求法
1.祖孙询问(倍增)
因为2^16>4e4,所以开15够了
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=4e4+10,M=2*N; int h[N],e[M],ne[M],idx; int n,m,root; int depth[N],f[N][16],q[N];//depth存的是每个节点的深度，f存的是以节点i开始跳2的j次方步到达的点 void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void bfs() { memset(depth,0x3f,sizeof depth);//初始化每个深度 int hh=0,tt=0; q[0]=root;//把根节点放进队列中 depth[0]=0,depth[root]=1;//初始化0为虚拟根，因为待会跳的话会跳出根节点，根节点就定义为第一层 while(hh<=tt) { int t=q[hh++]; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(depth[j]>depth[t]+1)//假如这个节点没被更新过 { depth[j]=depth[t]+1;//更新这个节点的深度 q[++tt]=j;//把这个点放进队列中 f[j][0]=t;//从j开始跳2^0=1步是t for(int k=1;k<=15;k++)//更新这个点跳的步数走到的点 f[j][k]=f[f[j][k-1]][k-1];//用递归的方式更新 } } } } int lca(int a,int b) { if(depth[a]<depth[b]) swap(a,b);//让a是深度最大的点 //让a跳到跟b同个深度 for(int i=15;i>=0;i--)//让a跳到跟b同个深度，从大的步数开始跳 if(depth[f[a][i]]>=depth[b]) a=f[a][i];//更新跳到的点 if(a==b) return b;//假如跳到了b，说明b是最近公共祖先 //在同一深度下一起跳2^i步来找公共祖先 for(int i=15;i>=0;i--) if(f[a][i]!=f[b][i]) { a=f[a][i];//更新跳到的点 b=f[b][i];//更新跳到的点 } return f[a][0];//因为是跳到公共祖先的下一层，则输出他们点的上一步就是公共祖先了 } int main() { cin>>n; memset(h,-1,sizeof h); while(n--) { int a,b; cin>>a>>b; if(b==-1) root=a; else add(a,b),add(b,a); } bfs();//先搜索一下深度和跳多少步到那个位置 cin>>m; while(m--) { int a,b; cin>>a>>b; int p=lca(a,b);//求一下公共祖先 if(p==a) puts("1"); else if(p==b) puts("2"); else puts("0"); } return 0; }
2.距离（tarjan+并查集）
tarjan是离线算法就是先把所有询问存下来，然后在求
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; #define x first #define y second const int N=2e5+10,M=2*N; int n,m; int h[N],e[M],ne[M],w[M],idx; int ans[N],dist[N];//ans是记录每个点的答案，diat存的是点跟1号点的距离 int st[N];//st存的是三种状态，0表示还没遍历过，1表示争做遍历，2表示已经遍历过 int p[N];//用来并查集 vector<pii> query[N];//第一个存的是询问的点，第二个存的是下标 void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void dfs(int u,int fa)//处理每个点跟1的距离 { for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa) continue; dist[j]=dist[u]+w[i]; dfs(j,u); } } int find(int x)//并查集 { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } void tarjan(int u) { st[u]=1;//标记这个点正在遍历 for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(!st[j])//假如没有遍历过 { tarjan(j);//则遍历一遍这个点 p[j]=u;//把这个点记录是跟u一个集合的 } } for(auto item:query[u])//处理所有询问 { int y=item.x,id=item.y;//y是询问的点，id是询问的位置 if(st[y]==2)//假如是遍历过的点 { int anc=find(y);//找一下是由那个点的集合，也就是最近公共祖先 ans[id]=dist[y]+dist[u]-2*dist[anc];//答案就是y与1距离加上u的距离减去最近公共祖先距离的两倍就是答案 } } st[u]=2;//标记这个点已经遍历过 } int main() { scanf("%d%d",&n,&m); memset(h,-1,sizeof h); for(int i=1;i<n;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c),add(b,a,c); } for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); if(a!=b)//假如相等则答案就是0，不用求 { query[a].push_back({b,i});//把a询问的b和下标i放进a询问中 query[b].push_back({a,i});//把b询问的a和下标i放进b询问中 } } dfs(1,-1);//处理每个点跟1号点的距离 for(int i=1;i<=n;i++) p[i]=i;//并查集初始化 tarjan(1);//做一遍Trajan算法 for(int i=0;i<m;i++) printf("%d\n",ans[i]); return 0; }
3.次小生成树(kruskal+倍增)
因为2^17>1e5，所以开17就行了
kruskal求最小生成树，倍增求两点之间的最大和次大边
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10,M=3e5+10,INF=0x3f3f3f3f; int p[N];//并查集 int h[N],e[M],ne[M],w[M],idx; int depth[N],d1[N][17],d2[N][17],f[N][17];//depth是深度，d1是某个点走2^j次方步的最大值，d2是次大值，f是某个点走2^k次方步所到达的点 int q[N]; int n,m; struct Edge { int a,b,w; bool used;//用来标记是否是树边 bool operator <(const Edge &t) const { return w<t.w; } }edge[M]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } ll kruskal()//求最小生成树 { memset(h,-1,sizeof h);//初始化 for(int i=1;i<=n;i++) p[i]=i;//初始化 sort(edge,edge+m);//排序 ll res=0; for(int i=0;i<m;i++) { int a=find(edge[i].a),b=find(edge[i].b),w=edge[i].w; if(a!=b)//假如不在一个集合 { p[a]=b;//合并成一个集合 res+=w;//加上这条最小生成树的边 edge[i].used=true;//标记一下是树边 add(edge[i].a,edge[i].b,w),add(edge[i].b,edge[i].a,w);//建树图 } } return res;//返回最小生成树的权值和 } void bfs()//求 深度 最大值 次大值 每个点走几步由那个点更新过来 { memset(depth,0x3f,sizeof depth); depth[0]=0,depth[1]=1;//0号点是避免跳出去，1号点初始化深度为1 int hh=0,tt=0; q[0]=1;//1号点入队 while(hh<=tt) { int t=q[hh++]; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(depth[j]>depth[t]+1)//假如没有更新过 { depth[j]=depth[t]+1;//则更新深度 q[++tt]=j;//把这个点入队 f[j][0]=t;//j这个点走2^0=1步是t d1[j][0]=w[i],d2[j][0]=-INF;//j这个点向上走2^0=1步的最大值是w[i],次大没有标记为负无穷 for(int k=1;k<=16;k++)//更新跳到的点 { int anc=f[j][k-1];//表示由那个点跳过来的 int d[4]={d1[anc][k-1],d2[anc][k-1],d1[j][k-1],d2[j][k-1]};//把j~anc~k的最大次大加到d中 f[j][k]=f[anc][k-1];//更新跳的点 d1[j][k]=d2[j][k]=-INF;//先初始化为负无穷 for(int u=0;u<4;u++)//求一遍最大和次大 { int dist=d[u]; if(dist>d1[j][k]) d2[j][k]=d1[j][k],d1[j][k]=dist; else if(dist!=d1[j][k]&&dist>d2[j][k]) d2[j][k]=dist; } } } } } } int lca(int a,int b,int w)//用来求最大值与次大值能否更新 { static int d[2*N]; int cnt=0; if(depth[a]<depth[b]) swap(a,b);//假如a深度低，则交换 for(int k=16;k>=0;k--)//让a与b同个深度 if(depth[f[a][k]]>=depth[b])//假如还是大，则继续跳 { //把他们跳过的位置的最大值与次大值都记录下来 d[cnt++]=d1[a][k]; d[cnt++]=d2[a][k]; a=f[a][k];//更新跳的点 } if(a!=b)//假如还没跳到一起，也就是没找到最近公共祖宗 { for(int k=16;k>=0;k--)//让a和b一起跳 if(f[a][k]!=f[b][k]) { //把他们跳过的位置的最大值与次大值都记录下来 d[cnt++]=d1[a][k]; d[cnt++]=d2[a][k]; d[cnt++]=d1[b][k]; d[cnt++]=d2[b][k]; a=f[a][k],b=f[b][k];//更新跳过的位置 } //最后也要把跳到最近公共祖先的位置也记录下来 d[cnt++]=d1[a][0]; d[cnt++]=d2[a][0]; d[cnt++]=d1[b][0]; d[cnt++]=d2[b][0]; } int dist1=-INF,dist2=-INF; for(int i=0;i<cnt;i++)//求一遍最大值和次大值 { int dist=d[i]; if(dist>dist1) dist2=dist1,dist1=dist; else if(dist!=dist1&&dist>dist2) dist2=dist; } if(w>dist1) return w-dist1;//假如最大值可以用来更新 if(w>dist2) return w-dist2;//反之次大值可以用来更新 return INF;//反之为正无穷 } int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int a,b,w; scanf("%d%d%d",&a,&b,&w); edge[i]={a,b,w}; } ll sum=kruskal();//求一下最小生成树的权值和 bfs();//求深度 最大值 次大值 更新的点 ll res=1e18; for(int i=0;i<m;i++) if(!edge[i].used)//假如是非树边 { int a=edge[i].a,b=edge[i].b,w=edge[i].w; res=min(res,sum+lca(a,b,w));//求一遍最大值与次大值能否用来更新 } printf("%lld\n",res); return 0; }
4. 闇の連鎖（倍增+树形差分）
c表示所有非树边构成的换的树边+1，假如该树边的c大于1 则说明得砍大于1的非树边，则不满足题意方案则+0，假如等于1，说明砍1条非树边就行则方案+1，假如等于0，说明不管怎么砍非树边都满足则+m
然后这题要用到树形差分就是d[x]+=c,d[y]+=c,d[p]-=c,p是x与y的最近公共祖先
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10,M=2e5+10; int h[N],e[M],ne[M],idx; int depth[N],f[N][17];//depth是深度，f是记录条几步条到的点 int q[N],d[N];//d存的就是c,就是树形差分 int ans,n,m;; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void bfs() { memset(depth,0x3f,sizeof depth); depth[0]=0,depth[1]=1;//0号点是虚拟原点，1号点让他为跟 int hh=0,tt=0; q[0]=1;//1号点放进队列中 while(hh<=tt) { int t=q[hh++]; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(depth[j]>depth[t]+1)//假如还没更新过 { depth[j]=depth[t]+1;//则更新 q[++tt]=j;//把这个点放进队列中 f[j][0]=t;//标记这个点的上一步是t for(int k=1;k<=16;k++)//更新条的其他步到达的点 f[j][k]=f[f[j][k-1]][k-1]; } } } } int lca(int a,int b) { if(depth[a]<depth[b]) swap(a,b);//假如a的深度小于b的则交换 for(int k=16;k>=0;k--)//让a跳到跟b同个深度 if(depth[f[a][k]]>=depth[b]) a=f[a][k];//更新跳到的点 if(a==b) return b;//假如b是最近公共祖先了，则返回 for(int k=16;k>=0;k--)//让a跟b一起跳 if(f[a][k]!=f[b][k]) a=f[a][k],b=f[b][k];//更新两个跳到的位置 return f[a][0];//返回他们的上一个就是最近公共祖先节点 } //该点的值就是子树的差分前缀和，跟其他差分一样都是差分前缀和就是该点的值 int dfs(int u,int fa)//返回值是子树差分值前缀和 { int res=d[u];//res记录的是树形前缀和，把这个点的差分也加上 for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa) continue;//避免重复搜索 int s=dfs(j,u);//s是j这个子树的差分前缀和 if(s==0) ans+=m;//假如是0则加上m else if(s==1) ans++;//假如是1则加1 res+=s;//把所有子树的差分都加上 } return res; } int main() { memset(h,-1,sizeof h); scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b),add(b,a); } bfs();//求一遍深度和跳到的点 for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); int p=lca(a,b);//求a跟b的公共祖先 d[a]++,d[b]++,d[p]-=2;//因为是差分，则a+1，b+1,p-2 } dfs(1,-1);//最后求一遍所有的方案 printf("%d\n",ans); return 0; }
