【树上倍增】CF294 div2 E A and B and Lecture Rooms

ゝ一纸荒年。 2024-03-17 10:48 26阅读 0赞

**虽然是道2100，但是思维难度好像也不是很高的样子....**

[Problem - 519E - Codeforces][]

题意：

给定一棵树和两个结点u和v，每次询问问整棵树上离u和v的距离一样的结点个数是多少

![70d7d957d40344f6b276c5759f450d33.png][]

思路：

对u和v分类讨论即可

如果u==v，那么整棵树都满足条件

如果dep\[u\]==dep\[v\]，那么如下图所示的结点x和结点y所在子树之外的所有结点都满足条件（图画的比较抽象qwq）

![f3ed674b57eb4acc8a5592e3a15e7633.jpeg][]

如果dep\[u\]!=dep\[v\]

先把u到v的路径中到u和v距离一样的点找出来：uu

vv是uu下面的那个结点

![f5413abf418b42f999bf46d9e8bf0ca7.jpeg][] 满足条件的就是uu这棵子树除去vv这颗子树的大小

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    int N,M,u,v,tot=0;
    int head[mxn];
    int F[mxn][33],dep[mxn],sz[mxn];
    
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    void dfs(int u,int fa){
    	sz[u]=1;
    	dep[u]=dep[fa]+1;
    	F[u][0]=fa;
    	for(int i=1;i<=30;i++) F[u][i]=F[F[u][i-1]][i-1];
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs(edge[i].to,u);
    		sz[u]+=sz[edge[i].to];
    	}
    }
    int lca(int u,int v){
    	if(dep[u]<dep[v]) swap(u,v);
    	for(int j=30;j>=0;j--){
    		if(dep[F[u][j]]>=dep[v]){
    			u=F[u][j];
    		}
    	}
    	if(u==v) return u;
    	for(int j=30;j>=0;j--){
    		if(F[u][j]!=F[v][j]){
    			u=F[u][j];
    			v=F[v][j];
    		}
    	}
    	return F[u][0];
    }
    void solve(){
    	cin>>N;
    	G_init();
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v;
    		add(u,v);
    		add(v,u);
    	}
    	dfs(1,0);
    	cin>>M;
    	for(int i=1;i<=M;i++){
    		cin>>u>>v;
    		if(u==v){
    			cout<<N<<'\n';
    			continue;
    		}
    		int LCA=lca(u,v);
    		if(dep[u]==dep[v]){
    			int dis=dep[u]-dep[LCA];
    			dis--;
    			int uu=u;
    			for(int j=30;j>=0;j--){
    				if((dis>>j)&1){
    					uu=F[uu][j];
    				}
    			}
    			int vv=v;
    			for(int j=30;j>=0;j--){
    				if((dis>>j)&1){
    					vv=F[vv][j];
    				}
    			}
    			cout<<N-sz[uu]-sz[vv]<<'\n';
    		}else{
    			if(dep[u]<dep[v]) swap(u,v);
    			int d1=dep[u]-dep[LCA];
    			int d2=dep[v]-dep[LCA];
    			if(abs(d1-d2)&1){
    				cout<<0<<'\n';
    			}else{
    				int dis=(d1+d2)/2;
    				int uu=u;
    				for(int j=30;j>=0;j--){
    					if((dis>>j)&1){
    						uu=F[uu][j];
    					}
    				}
    				int vv=u;
    				dis--;
    				for(int j=30;j>=0;j--){
    					if((dis>>j)&1){
    						vv=F[vv][j];
    					}
    				}
    				cout<<sz[uu]-sz[vv]<<'\n';
    			}
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - 519E - Codeforces]: https://codeforces.com/problemset/problem/519/E
[70d7d957d40344f6b276c5759f450d33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/b6615cc219c24b619f15b06ea428a215.png
[f3ed674b57eb4acc8a5592e3a15e7633.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/e7b5563003f047b9832bfaafb8fd9be7.png
[f5413abf418b42f999bf46d9e8bf0ca7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/6974b276bf5c4e3b9142c395269bf565.png