UOJ #297. 一样远
Description本题没有背景嘤嘤嘤。给一棵树以及树上的两个点，问树上到这两个点距离相同的点的个数。
Input第一行一个整数N代表点的个数。接下来N-1 行，每行两个数字F和T，表示F和T之间有一条边。接下来一行一个整数 M 代表询问次数。接下来 M 行，每行两个数字 A 和 B，表示这次询问 A 和 B（A 可能与 B 相同）。
Output输出 M 行，每行一个整数表示到 A 和 B 一样远的点个数。
Sample Input4
1 2
2 3
2 4
2
1 2
1 3Sample Output0
2Hint10% 的数据，N,M=030% 的数据：N,M≤1000；100% 的数据：1≤N,M≤100000,保证树的形态随机
Time Limit&Memory LimitTime Limit :1sMemory Limit : 256M本题直接找两点的距离中点即可,注意:若两点距离为奇数则无解.
若有中点,将两点跳到中点的子节点,分别即为u,v,当两点深度相同时,ans=n-size[u]-size[v]
当两点深度不同时,ans=size[fa[u]]-size[u](这里定义u为较深的那个节点,fa[u]即为两节点中点).Code:
#include
#include
#include
#include
#include
#include
using namespace std;
const int M=100005;
const int N=17;
int n,m,fa[M][N],dep[M],son[M];
vector G[M];
void dfs(int u){for(int i=0;idep[v]){u=up(u,dep[u]-dep[v]);}if(u==v){return u;}for(int i=16;i>=0;i--){if(fa[u][i]!=fa[v][i]){u=fa[u][i];v=fa[v][i];}}return fa[u][0];
}
int result(int u, int v){if(u==v){return n;}else{if(dep[u] 转载于:https://www.cnblogs.com/ukcxrtjr/p/11503956.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！