MYF

Codeforces 519E A and B and Lecture Rooms

Posted on | In | | Visitors

题目链接

codeforces 519E

解题方法：LCA

题目分析

题目大意

给定一棵树，每一条边的权值都为1，问给定两个点，到该两点距离相等的点有多少个。

解析

一开始并不那么容易想到用lca解决这个问题。但是转化一下，就变成了lca的问题。

对于树上的任意两个点，他们之间的直接距离为dis，那么很明显dis就是dep[x]+dep[y]-2*dis[lca(x, y)]。当dis为奇数时，我们无法找到两者的中点。dis为偶数时，可以分为两种情况，第一种，dep[x]和dep[y]相等的情况，那么就是除了x和y所在的两个子树的所有节点都可以。另一种是dep[x]>dep[y]（同理dep[y]>dep[x]），先找到两者的中间点mid，然后mid的所有子节点的数量减去x所在的mid的子树的节点数量即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define pb push_back
#define mp make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int N = 100005;

int n , m , pre[N] ,rt[N], mcnt;
bool vis[N];
struct edge
{
    int x , next;
} e[N << 1];

int dep[N] , f[17][N] , Lev , s[N];///1<<16 < N, f[j][i] 表示i的第2^j个祖先

void dfs(int x , int fa)///也可以用bfs，但bfs不能统计节点孩子个数
{
    dep[x] = dep[fa] + 1;
    f[0][x] = fa , s[x] = 1;
    for (int i = pre[x] ; ~i ; i = e[i].next)
    {
        int y = e[i].x;
        if (y != fa)
        {
            dfs(y , x);
            s[x] += s[y];///节点x的孩子个数
        }
    }
}
void bfs(int rt)///不需要求孩子个数，同时防止暴栈
{
    queue<int> q;
    q.push(rt);
    f[0][rt] = 0,dep[rt] = 1,vis[rt] = 1;
    while(!q.empty())
    {
        int fa = q.front();
        q.pop();
        for (int i = pre[fa] ; ~i ; i = e[i].next)
        {
            int x = e[i].x;
            if (!vis[x])
            {
                dep[x] = dep[fa] + 1;
                f[0][x] = fa ,vis[x] = 1;
                q.push(x);
            }
        }
    }
}
int LCA(int x , int y)
{
    if (dep[x] > dep[y]) swap(x , y);
    for (int i = Lev ; i >= 0 ; -- i)///找y的第dep[y] - dep[x]个祖先
        if (dep[y] - dep[x] >> i & 1)
            y = f[i][y];
    if (x == y) return y;
    for (int i = Lev ; i >= 0 ; -- i)
        if (f[i][x] != f[i][y])
            x = f[i][x] , y = f[i][y];
    return f[0][x];
}
int get_kth_anc(int x , int k) ///找x的第k个祖先
{
    for (int i = 0 ; i <= Lev ; ++ i)
        if (k >> i & 1)
            x = f[i][x];
    return x;
}
void init()
{
    memset(pre , -1 , sizeof(pre));
    memset(rt,0,sizeof(rt));
    mcnt = 0;
}
void addedge(int x,int y)
{
    e[mcnt].x = y,
    e[mcnt].next = pre[x],
    pre[x] = mcnt ++;
}
int main()
{
    while (scanf("%d",&n)!=EOF) {
        int i , j , x , y , z,anc;
        init();
        for (i = 1 ; i < n ; ++ i)
        {
            scanf("%d%d",&x,&y);
            addedge(x,y);
            addedge(y,x);
            rt[y]  =x;
        }
        for(int i=1; i<=n; i++)
        {
            if(rt[i]==0)
            {
                anc = i;
                break;
            }
        }
        dfs(anc , 0);
        for (j = 1 ; 1 << j < n ; ++ j)
            for (i = 1 ; i <= n ; ++ i)
                f[j][i] = f[j - 1][f[j - 1][i]];
        Lev = j - 1;
        int k;
        scanf("%d",&k);
        while (k--) {
            scanf("%d%d",&x,&y);
            if (dep[x] < dep[y])
                swap(x , y);
            if (x==y) {
                cout<<n<<endl;
            }
            else if ((dep[x]-dep[y])%2){
                cout<<0<<endl;
            }
            else if (dep[x]==dep[y]){
                int lca = LCA(x, y);
                int xx = get_kth_anc(x, dep[x]-dep[lca]-1);
                int yy = get_kth_anc(y, dep[y]-dep[lca]-1);
                cout<<n-s[xx]-s[yy]<<endl;
            }
            else{
                int dis = dep[x] + dep[y] - dep[LCA(x, y)]*2;
                int mid = get_kth_anc(x, dis/2);
                int xx = get_kth_anc(x, dis/2-1);
                cout<<s[mid]-s[xx]<<endl;
            }
        }
    }
    
    return 0;
}