【链接】 我是链接,点我呀:)
【题意】
在这里输入题意
【题解】
最近公共祖先。
(树上倍增
一开始统计出每个子树的节点个数_size[i]
如果x和y相同。
那么直接输出n.
否则求出x和y的最近公共祖先。z
(假定y的深度大于x
【1】如果z等于x或y中的一个。
那么久就找到x..y的路径(长度设为L)中的中点u。
显然,u和它的其他len-1个子树上的任意一个节点都是可行的(除了那个包含y的子树
设_get(x,step)表示x节点往上走step步到达的节点
则输出_sum[中点]-_sum[ _get(y,L/2) ]即可
【2】如果z不等于x和y中的任意一个。
①x和y往上走的距离是一样的。
->那么z的子树中,除了这两个节点往上走上来的子树,
其他子树里面的节点都是可行的
②x和y往上走的距离不一样。
->那么就还是和【1】中的情况一样,找出中点即可。
_get(x,step)函数可以用树上倍增的p数组实现。
【代码】
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
const int MAX = 17;
vector <int> son[MAXN],g[MAXN];
int n,p[MAXN][MAX+5],dep[MAXN],pre[MAX+5],m;
int _size[MAXN];
void dfs(int x,int f)
{
_size[x] = 1;
dep[x] = dep[f] + 1;
p[x][0] = f;
for (int i = 1; i <= MAX; i++) p[x][i] = p[p[x][i - 1]][i - 1];
int len = g[x].size();
for (int i = 0; i <= len - 1; i++)
{
int y = g[x][i];
if (y != f) {
son[x].push_back(y);
dfs(y, x);
_size[x]+=_size[y];
}
}
}
int _get(int x,int ma){
for (int i = MAX;i>=0;i--){
if (ma>=pre[i]){
ma-=pre[i];
x = p[x][i];
}
}
return x;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
#ifdef LOCAL_DEFINE
freopen("rush.txt","r",stdin);
#endif
pre[0] = 1;
for (int i = 1; i <= MAX; i++)
pre[i] = pre[i - 1] << 1;
cin >> n;
for (int i = 1; i <= n; i++)
son[i].clear();
for (int i = 1; i <= n - 1; i++)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 0);
cin >> m;
for (int i = 1; i <= m; i++)
{
int t0, t1,pret1,pret0;
cin >> t0 >> t1;
if(t0==t1){
cout<<n<<endl;
continue;
}
if (dep[t0] > dep[t1]) swap(t0, t1);
pret1 = t1;
pret0 = t0;
int dist0 = 0,dist1 = 0;
for (int i = MAX; i >= 0; i--)
if (dep[t0] <= dep[t1] - pre[i]){
t1 = p[t1][i];
dist1 += pre[i];
}
//t1��t0����ͬһ�߶�
if (t1 == t0)
{
if ((dist0+dist1)%2==0){
int dis = (dist0+dist1)/2;
int special = _get(pret1,dis);
cout << _size[special] - _size[_get(pret1,dis-1)]<<endl;
}else{
cout<<0<<endl;
}
continue;
}
for (int i = MAX; i >= 0; i--)
{
if (p[t0][i] == p[t1][i]) continue;
dist0+=pre[i];dist1+=pre[i];
t0 = p[t0][i], t1 = p[t1][i];
}
dist0+=pre[0],dist1+=pre[0];
t0 = p[t0][0];
if (dist0==dist1){
cout << _size[1]-_size[_get(pret0,dist0-1)]-_size[_get(pret1,dist1-1)] << endl;
}else{
if ((dist0+dist1)%2==0){
int dis = (dist0+dist1)/2;
int special = _get(pret1,dis);
cout << _size[special] - _size[_get(pret1,dis-1)]<<endl;
}else{
cout<<0<<endl;
}
}
}
return 0;
}