本文共 1073 字，大约阅读时间需要 3 分钟。
传送门：
题意：给定一棵树，每次询问到达点u,v距离相等的点有多少个。
分析:按情况考虑：
1.abs(deep[u]-deep[v])%2==1时，必定不存在到达u,v距离相等的点。
2.如果deep[u]==deep[v]时，ans=n-num[lca(u,v)u在的儿子树]-num[lca(u,v)v在的儿子树]。
3.如果deep[u]!=deep[v]时，在u到v的路径中找出到达u,v相等的节点x，则ans=num[x]-num[u在的x儿子树].
#include #include #include #include #include #include #include #define N 200010#define LL long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;struct edge{ int v,next; edge() {} edge(int v,int next):v(v),next(next) {}} e[N];int head[N],tot;int num[N],deep[N];int fa[N][20];void init(){ memset(head,-1,sizeof(head)); tot=0;}void addedge(int u,int v){ e[tot]=edge(v,head[u]); head[u]=tot++;}void dfs(int x,int f){ for(int i=1; i<20; i++) { if(deep[x]<(1< =0; i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } if(x==y)return x; return fa[x][0];}int main(){ int n,m; while(scanf("%d",&n)>0) { init(); for(int i=1; i
转载于:https://www.cnblogs.com/lienus/p/4306534.html
