（20210321备份）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
ll read()
{
ll res=0,f=1;
char c=getchar();
while(!isdigit(c) && c!='-') c=getchar();
if(c=='-') f=-1,c=getchar();
while(isdigit(c)) res=(res<<1)+(res<<3)+c-48,c=getchar();
return res*f;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
return 0;
}
//★☆
/*
BV1B7411e76f
BV1kE41127Ff
山田一郎：木村昴
山田二郎：石谷春贵
山田三郎：天崎滉平
碧棺左马刻：浅沼晋太郎
入间銃兎：驹田航
毒岛メイソン理鶯：神尾晋一郎
飴村乱数：白井悠介
梦野幻太郎：斉藤壮马
有栖川帝统：野津山幸宏
神宫寺寂雷：速水奨
伊弉冉一二三：木岛隆一
観音坂独歩：伊东健人
*/
/*
srand((unsigned)time(0)); //随机数初始化
-O2 -std=c++11 -Wl,--stack=2100000000
ios::sync_with_stdio(false);
system("pause"); //按任意键继续
#define PI 3.1415926 //宏定义
getline(cin,s); //字符串读入
cout<<setiosflags(ios::fixed)<<setprecision(2); //保留两位小数
double //双浮点
ios::sync_with_stdio(false);//优化,使cin与scanf相差无几
lower_bound( a.begin,a.end,a.num)-a-1
//从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，
找到返回该数字的地址，不存在则返回end。
通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( a.begin,a.end,a.num)-a-1
//从数组的begin位置到end-1位置二分查找第一个大于num的数字，
找到返回该数字的地址，不存在则返回end。
通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
fclose(stdin); //关闭freopen in
fclose(stdout); //关闭freopen out
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<utility>
int read()
{
int res=0;
int f=1;
char c=getchar();
while(!isdigit(c) && c!='-') c=getchar();
if(c=='-') f=-1,c=getchar();
while(isdigit(c)) res=(res<<1)+(res<<3)+c-48,c=getchar();
return res*f;
}
void print(ll x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9) print(x/10);
putchar(x%10+'0');
}
dij：
void dij(int x)
{
priority_queue<pr,vector<pr>,greater<pr> > q;
for(int i=1;i<=n;i++)
{
dis[i]=1e9*(i!=x);
}
q.push(pr(dis[x],x));
while(!q.empty())
{
pr now=q.top();q.pop();
int u=now.second;
if(dis[u]<now.first) continue;
for(int i=head[u];i;i=e[i].nt)
{
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
q.push(pr(dis[v],v));
}
}
}
}
组合数：
ll poww(ll x,ll n,ll mod)
{
ll res=1;
while(n)
{
if(n&1) res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
ll fac[maxn*3],inv[maxn*3];
ll C(int n,int m)
{
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
fac[0]=inv[0]=1;
for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
inv[n]=poww(fac[n],mod-2,mod);
for(int i=n-1;i;i--) inv[i]=inv[i+1]*(i+1)%mod;
线性筛：
void shai(int n)
{
for(int i=2;i<=n;i++)
{
if(!isp[i]) P[++tot]=i;
for(int j=1;j<=tot && i*P[j]<=n;j++)
{
isp[i*P[j]]=1;
if(i%P[j]==0) break;
}
}
return ;
}
筛
int tot;
int p[maxn];
bool isprime[11000000];
void P(int n)
{
memset(isprime,true,sizeof isprime);
isprime[1]=false;
for(ll i=2;i<=n;i++)
if(isprime[i])
{
p[++tot]=i;
ll j=i*i;
while(j<=n)
{
isprime[j]=false;
j+=i;
}
}
}
Lca:
int f[maxn][30];
int dep[maxn],lg[maxn];
void dfs(int x,int fa)
{
f[x][0]=fa;
dep[x]=dep[fa]+1;
for(int i=1;i<=lg[dep[x]];i++) f[x][i]=f[f[x][i-1]][i-1];
for(int i=head[x];i;i=e[i].nt)
{
int to=e[i].to;
if(to==fa) continue;
dfs(to,x);
}
}
int Lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=f[x][lg[dep[x]-dep[y]]-1];
if(x==y) return x;
for(int i=lg[dep[x]]-1;i>=0;i--)
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
return f[x][0];
}
int n=read(),m=read(),rt=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y);add(y,x);
}
for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
dfs(rt,0);
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
printf("%d\n",Lca(x,y));
}
//kruskal:
struct node
{
int u,v,d;
}e[200010];
bool cmp(node a,node b)
{
return a.d<b.d;
}
int getfa(int x)
{
if(f[x]==x) return x;
return f[x]=getfa(f[x]);
}
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].d;
for(int i=1;i<=n;i++) f[i]=i;
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;i++)
{
int fu=getfa(e[i].u),fv=getfa(e[i].v);
if(fu==fv) continue;
f[fu]=fv;
tot+=e[i].d;
}
cout<<tot<<endl;
//压位高精模板！
struct yawei_int
{
int len=1,a[110];
inline void operator += (const yawei_int &ot)
{
len=max(len,Other.len);
for(int i=1;i<=len;i++)
{
a[i]+=ot.a[i];
if (a[i]>=base)
{
a[i+1]++;
a[i]-=base;
}
}
if(a[len+1]>0) len++;
}
inline void print()
{
printf("%d",a[len]);
for(int i=len-1;i;i--)
{
printf("%09d",a[i]);
}
puts("");
}
} a[maxn];
动态开点线段树板子（不保证正确性awa）
struct node
{
node *left;
node *right;
int sum;
};
typedef node* nodep;
int query(node *a,int l,int r,int u,int v)
{
if(a==NULL) return 0;
if(l>v || r<u) return 0;
if(u<=l && r<=v) return a->sum;
int mid=(l+r)/2;
return query(a->left,l,mid,u,v)+query(a->right,mid+1,r,u,v);
}
void change(nodep &a,int l,int r,int x,int e)
{
if(x<l || x>r) return ;
if(a==NULL)
{
a=malloc(sizeof(node));
reutrn;
}
int mid=(l+r)/2;
change(a->left,l,mid,x,e);
change(a->right,mid+1,r,x,e);
a->sum+=e;
}
欧拉函数（根号复杂度，需配合筛食用）
ll phi(ll n)
{
ll sum=n;
for(ll i=1;p[i]*p[i]<=n;i++)
if(n%p[i]==0)
{
sum=sum-sum/p[i];
while(n%p[i]==0)
n=n/p[i];
}
if(n>1) sum=sum-sum/n;
return sum;
}
欧拉函数 （线性，存在phi中）
int tot;
int isp[maxn*20];
int p[maxn*10],phi[maxn*10];
void pre(int n)
{
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!isp[i])
{
p[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot && p[j]*i<=n;j++)
{
isp[i*p[j]]=1;
if(i%p[j])
phi[i*p[j]]=phi[i]*(p[j]-1);
else
{
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}
}
算mu：（线性）
void getmu(int n)
{
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!isp[i])
{
mu[i]=-1;
p[++tot]=i;
}
for(int j=1;j<=tot && i*p[j]<=n;j++)
{
isp[i*p[j]]=1;
if(i%p[j]) mu[i*p[j]]=-mu[i];
else break;
}
}
}
*/
0 条评论