Codeforces 519 E. A and B and Lecture Rooms

Description

询问一个树上与两点距离相等的点的个数.

Sol

倍增求LCA.

一棵树上距离两点相等,要么就只有两点的中点,要么就是与中点相连的所有点.

有些结论很容易证明,如果距离是偶数,那么他们没有中点,树上不存在距离两点相等的点.

如果中点恰好是两点LCA,那么答案就是\(n-size_x-size_y\) ,\(size_x\) 和 \(size_y\) 表示LCA的子节点中子树包含 \(u,v\) 的子节点的\(size\)

如果不是LCA,那么答案就是 \(size_{LCA}-size_x\) 是深度靠下的点.

PS:Loli的破机子跑的真tm慢.

Code

#include<cstdio>
#include<utility>
#include<vector>
#include<iostream>
using namespace std; #define mpr(a,b) make_pair(a,b)
#define debug(a) cout<<#a<<"="<<a<<" "
const int N = 100005;
const int M = 21; int n;
int f[N][M],d[N],sz[N],pow2[M];
vector<int> g[N]; inline int in(int x=0,char ch=getchar()){ while(ch>'9'|| ch<'0') ch=getchar();
while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
void DFS(int u,int fa,int dep){
f[u][0]=fa,sz[u]=1,d[u]=dep;
for(int i=0,v;i<g[u].size();i++) if((v=g[u][i])!=fa){
DFS(v,u,dep+1);
sz[u]+=sz[v];
}
}
pair<int,int> LCA(int u,int v){
if(d[u]<d[v]) swap(u,v);
int l=d[u]-d[v],res=0;
for(int i=0;i<M;i++){
if(l&pow2[i]) res=res+pow2[i],u=f[u][i];
}
if(u==v) return mpr(res,u);
for(int i=M-1;~i;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i],res+=pow2[i]*2;
return mpr(res+2,f[u][0]);
}
int Getp(int u,int d){
for(int i=0;i<M;i++) if(d & pow2[i]) u=f[u][i];
return u;
}
void solve(int u,int v){
if(d[u]<d[v]) swap(u,v);
pair<int,int> pr=LCA(u,v); // debug(pr.first),debug(pr.second)<<endl; if(u==v){ printf("%d\n",n);return; }
if(pr.first & 1){ printf("%d\n",0);return; } int mid=Getp(u,pr.first/2);
int uu=Getp(u,pr.first/2-1),vv=Getp(v,pr.first/2-1); // debug(mid),debug(uu),debug(vv)<<endl; if(mid == pr.second){
printf("%d\n",n-sz[uu]-sz[vv]);
}else{
printf("%d\n",sz[mid]-(f[uu][0]==mid ? sz[uu] : 0) - (f[vv][0]==mid ? sz[vv] : 0));
}
}
int main(){ n=in();
for(int i=1,u,v;i<n;i++) u=in(),v=in(),g[u].push_back(v),g[v].push_back(u);
pow2[0]=1;for(int i=1;i<M;i++) pow2[i]=pow2[i-1]<<1; DFS(1,0,1);
for(int j=1;j<M;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1]; for(int m=in(),u,v;m--;) u=in(),v=in(),solve(u,v);
return 0;
}

  

上一篇:Java注释@interface的用法


下一篇:常用的jquery遍历函数