CodeForces 519E A and B and Lecture Rooms

发表于   |   分类于   |     |   阅读次数

题目大意

给出一颗无向有边权树，求到两点x,y距离相等的节点数。经典的LCA倍增算法模板。

题目链接CodeForces 519E

题意解析

求到两节点的距离想的的节点数，最普遍的解法是for循环遍历所有节点，对每一个节点z,
分别求z到两节点的距离，如果相等，counter变量就加1，然后输出counter。但不幸的是，数据很大，
这种解法会超时。为什么要用倍增算法？因为倍增算法可以顺便求出某节点的孩子的个数，还能求出
某节点的第K个祖先。通过这两个信息，我们可以不遍历所有点而直接求出答案。
首先奇偶剪枝，当x,y两点间距离为奇数时一定不存在这样的点（你可以随便画个树分析一下）。
其次，设s[]数组储存了某节点孩子数。
当x,y到LCA(x,y)的距离相等时，节点数为n-s[x1]-s[y1]（x1为x的LCA-1倍祖先，y1为y的LCA-1倍祖先）。
不相等时，设y为较深的节点，节点数为s[y3]-s[y2]（y3是a,b两点的中点节点，y2是y3与y相连边上的子节点）。

附加AC代码

LCA倍增算法详解

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
162
163
164
165
166
167
168
169
170
171
172
173
#pragma comment(linker, "/STACK:10240000000,10240000000")
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
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];
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!=-1 ; 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)//dep[y]-dep[x]刚好比2的i次方大时
                {
                        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 ++;
}
void work()
{
        int i , j , x , y , z, anc;
        init();
        scanf("%d", &n);
        for (i = 1 ; i < n ; ++ i)
        {
                scanf("%d%d", &x, &y);
                addedge(x, y);
                addedge(y,x);
                rt[y]  = x;
        }
        for (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;
        scanf("%d",&m);
        while(m--)
        {
                scanf("%d%d", &x, &y);
                if(x==y)
                {
                        printf("%d\n",n);
                        continue;
                }
                if (dep[x] > dep[y])
                {
                        swap(x , y);
                }
                int pos=LCA(x,y);
                int dis=dep[x]+dep[y]-2*dep[pos];
                if(dis%2==1)
                {
                        printf("0\n");
                }
                else
                {
                        dis/=2;
                        if(dep[x]==dep[y])
                        {
                                int x1=get_kth_anc(x,dis-1);
                                int y1=get_kth_anc(y,dis-1);
                                printf("%d\n",n-s[x1]-s[y1]);
                        }
                        else
                        {
                                int y1=get_kth_anc(y,dis-1);
                                int y2=get_kth_anc(y,dis);
                                printf("%d\n",s[y2]-s[y1]);
                        }
                }
        }
}
int main()
{
        work();
        return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！