Problem 给一棵树，，含有的距离相同。Limits Look up Original Problem From hereSolution 求出三种情况讨论，求出答案即可。答案与不同子树含有的节点总数有关，需要预处理。Complexity My Code;ll;ld;Edge{int from,to,next;}edge[MAXN];int head[N],num_edge;void add_Edge(int from,int to){int t=++num_edge;edge[t].from=from;edge[t].to=to;edge[t].next=head[from];head[from]=t;}int n,m,dfs_num;int anc[N][M],height[N],father[N],fatheredge[N],nodeval[N];void dfs_tree(int now,int fa,int h){height[now]=h;int num1=++dfs_num;for(int i=head[now];i!=-1;i=edge[i].next){int to=edge[i].to;if(to==fa){father[now]=fa;fatheredge[now]=i;continue;}dfs_tree(to,now,h+1);}nodeval[now]=dfs_num-num1+1;}void LCM_init(){repin(i,1,n){for(int j=0;1<<j<n;j++){anc[i][j]=-1;}}repin(i,1,n){anc[i][0]=father[i];}for(int j=1;1<<j<n;j++){repin(i,1,n){if(anc[i][j-1]!=-1) anc[i][j]=anc[anc[i][j-1]][j-1];}}}int find_LCA(int x,int y){if(height[x]<height[y]) swap(x,y);int log;for(log=0;1<<log<n;log++);log–;depin(i,log,0){if(height[x]-(1<<i)>=height[y]) x=anc[x][i];}if(x==y) return x;depin(i,log,0){if(anc[x][i]!=-1 && anc[x][i]!=anc[y][i]){x=anc[x][i];y=anc[y][i];}}return father[x];}int find_ans(int& x,int limith){int log;for(log=0;1<<log<n;log++);log–;depin(i,log,0){if(height[x]-(1<<i)>limith) x=anc[x][i];}int x1=father[x];return nodeval[x1];}int main(){scanf(“%d”,&n);repin(i,0,n){head[i]=-1;}repin(i,1,n-1){int a,b;scanf(“%d %d”,&a,&b);add_Edge(a,b);add_Edge(b,a);}dfs_tree(1,0,0);LCM_init();scanf(“%d”,&m);while(m–){int x,y,ans=0;scanf(“%d %d”,&x,&y);int lca=find_LCA(x,y);int leftdis=height[x]-height[lca];int rightdis=height[y]-height[lca];if(x==y) ans=n;else if((leftdis+rightdis)%2) ans=0;else if(leftdis==rightdis){ans=n;find_ans(x,height[lca]+(leftdis-rightdis)/2);ans-=nodeval[x];find_ans(y,height[lca]+(rightdis-leftdis)/2);ans-=nodeval[y];}else if(leftdis>rightdis){ans=find_ans(x,height[lca]+(leftdis-rightdis)/2);ans-=nodeval[x];}else{ans=find_ans(y,height[lca]+(rightdis-leftdis)/2);ans-=nodeval[y];}printf(“%d\n”,ans);}}
逆境磨练人、逆境是老师、逆境之苦可变甜。
