Kalzn
Kalzn
文章22
标签14
分类7
回到首页
博客归档
CSDN博客
戳我看荧
博客迁移说明
关于博主
© 2024 Kalzn Powered by Hexo & Nexmoe 本站总访问量次 本站访客数人次
点分树(动态点分治)

点分树(动态点分治)
2020年09月26日 算法竞赛

前置知识

点分治

吐槽

不知道为什么，网上有关点分树的讲解不多。而且都写的很简单（快哭了）。憨批实在是不懂。于是只能按照他们所给的思想手撸代码了。

讲解

我们在点分治中，使用了分治的思想，对于每个子树求解，我们都不会直接递归，而是找到重心后，从重心开始递归。这样在一些极端样例（一条链）的情况，仍能保证不会退化为。这是一个很神奇的分治方式。这时我们试想这么一道题目：

给你一颗n个节点树（n<1e5），给你m次询问（m<1e5），你需要回答出与x节点的距离小于等于k的节点的数量。

可以试想，如何使用点分治解决。但是发现，这是比较困难的，因为我们在点分治时，每次对子树进行分治，就会同时把情况局限在这棵子树中。也就是说，我们统计x点。我们只能统计出以x为根的子树中与他距离是k的点的个数。在加之每次询问的x和k都不一样。于是我们只能这么做：强行把x设置为整颗树的根节点，然后递归进行统计（所以这又有什么意义呢？这已经不是点分治了）。所以我们考虑点分树。

所谓点分树，是依照原树建立的一颗特别的树。我们回忆，在进行点分治的时候，会不断的寻找树的重心，我们先不考虑求解过程，只考虑点分治的寻找重心的过程。 在点分治过程中：会寻找树的重心，以它为树的根节点，然后递归它的所有子树，进行同样的操作，直到只剩一个节点。针对这个过程，我们这么建立一颗点分树：把一颗树根节点的所有子树中找到重心链接到这棵树的根节点。

简单的说就是：我们把所有子树的重心都链接到上一层树重心上。如图： 在这里插入图片描述

在这张图中，实线代表树的原边，虚线是其一个点分树，由子节点指向父节点。

我们得到这样一颗树有什么用呢？我们再次细想我们刚刚说为什么点分治处理这个题很困难，这是因为每次对子树进行分治，就会同时把情况局限在这棵子树中。所以我们需要想树形dp那样，统计它以及它的所有祖先的所有贡献。我们试想暴力：直接在原树上从x开始跳祖先，答案就是：x子树中所有距离x小于等于k的节点的数量+fa[x]子树中所有不在x子树中，距离fa[x]小于等于k-1的节点数量+.....一直跳到某个祖先y，满足dis（x，y）>k 停止。这种跳法在极端样例下会卡到所有我们要建立点分树，在点分树中跳祖先。答案即为下式点集的大小：

为或的祖先

其中dis(X,D)为点X与点D的距离。这样我们就可以通过维护某一个数据结构，使得复杂度在下求解。其中为数据结构每次查询的复杂度函数。

下面看几道模板题：

例一

P6329 【模板】点分树 | 震波

这个题虽然注明为点分树模板,但是难度相较例二，个人感觉比较大。

与向上面的例题非常类似（只是每个点加一个权值，而且有修改），这里我们使用的数据结构式线段树，单次查询为所有最终时间复杂度为。这里值得注意的是集合去重的做法。我的做法是每个节点维护两个线段树：

第一个线段树：为跳到该节点需要累计的不同距离的数量。

第二个线段树，为跳到给阶段的父节点，需要减去（去重）的不同数量。

第一个我们在点分治的时候跑子树所有点到该点距离的时候插入即可。第二个线段树的维护，我们现在统计x节点的第二个线段树，我们需要执行插入：

1
insert( root[x + n], dis(fa[x], u), val[u]);

其中root[x+ n]是x节点第二个线段树的根节点，对于子树上的每个节点u，我们在这个线段树的dis(fa[x], u)（x的点分树父节点到u节点在原树上的距离）位置插入val[u]（u的权值）。why？因为这些点，在从u->fa[u]跳的过程中，已经在u节点算过了，我们如果跳了u的父节点，就必须把这些节点减去。 这里可以看到ask函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int mask(int x, int k)
{
    int ans = 0;
    for (int c = x; c; c = fa[c])
    { //从x节点开始跳祖先直至点分树根节点
        int g = tdis(x, c); //计算x到目前c祖先节点的距离
        if (k - g >= 0) //如果k-g>=0，说明以c为根的子树需要被累计，
        				// 那些在原树上距离c小于等于k-g的节点需要被累计
            ans +=  ask( root[c], 0,  k- g);
        int cc;
        if(fa[c] &&  k - (cc = tdis(x, fa[c]) ) >= 0)
        { //c不是点分树根节点，且c的父节点仍需要被累计，此时把多算的节点给减去。
            ans -=  ask( root[c + n], 0, k- cc);
        }
    }
    return ans;
}

此时我们完成了查询，接下来是修改，要明白，可修改才是点分树的精髓所在（不然为啥交动态点分治），我们仍然先考虑暴力：和查询一样，一个点被修改，我们需要在原树上跳祖先，完成祖先的修改，而在动态点分治中，我们考虑跳点分树。 

1
2
3
4
5
6
7
8
9
10
11
12
void mchange(int x, int k)
{
    int g = -val[x] + k; //计算查找。
    val[x] = k;
    for (int c = x; c; c = fa[c])
    {//修改第一颗线段树的值
        insert( root[c], tdis(x, c), g);
        if (fa[c]) //如果c不是点分树根节点，第二个线段树也要被修改。
             insert( root[c + n], tdis(x, fa[c]), g);
    }
    return;
}
下面是ac代码(常数很大快哭了，开O2可以卡过，可用ST表优化)： 
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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
// % everyone
#include<cstdio>
#include<iostream>
#include<cstring>
#include <map>
#include <queue>
#include <set>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <bitset>
#include <array>
#include <cctype>
#include <time.h>


void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); }
void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); }
void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; }
template <typename T>
bool bacmp(const T & a, const T & b) { return a > b; }
template <typename T>
bool pecmp(const T & a, const T & b) { return a < b; }

#define ll long long
#define ull unsigned ll
#define _min(x, y) ((x)>(y)?(y):(x))
#define _max(x, y) ((x)>(y)?(x):(y))
#define max3(x, y, z) ( max( (x), max( (y), (z) ) ) )
#define min3(x, y, z) ( min( (x), min( (y), (z) ) ) )
#define pr(x, y) (make_pair((x), (y)))
#define pb(x) push_back(x)
using namespace std;
const int N = 1e5+5;
const int Z = 1e5+5;
int ver[N<<1], he[N], ne[N<<1];
int tot, rt, sum;
int siz[N], dis[N], mp[N];
bool vis[N];
int val[N]; int fa[N];
int n, m;
struct Node
{
    int l, r;
    int val;
}tr[N * 60];
int Tcnt;
int root[N<<1];
void insert(int &p, int pos, int v, int l = 0, int r = Z)
{
    if (!p) p = ++Tcnt;
    if (l == r)
    {
        tr[p].val += v;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) insert(tr[p].l, pos, v, l, mid);
    else insert(tr[p].r, pos, v, mid + 1, r);
    tr[p].val = tr[tr[p].l].val + tr[tr[p].r].val;
}
int ask(int p, int cl, int cr, int l = 0, int r = Z)
{
    
    if (p == 0) return 0;
    if (cl <= l && r <= cr)  return tr[p].val;
    int mid = (l + r) >> 1;
    int val = 0;
    if (cl <= mid) val += ask(tr[p].l, cl, cr, l, mid);
    if (cr > mid) val += ask(tr[p].r, cl, cr, mid+1, r);
    return val;
}
void add(int x, int y)
{
    ver[++tot] = y;
    ne[tot] = he[x];
    he[x] = tot;
}
int ff[N][18];
int d[N];
void bfs()
{
    queue<int> q;
    d[1] = 1;
    q.push(1);
    while(q.size())
    {
        int te = q.front();
        q.pop();
        for (int i = he[te]; i; i = ne[i])
        {
            int v = ver[i];
            if (d[v]) continue;
            d[v] = d[te] + 1;
            ff[v][0] = te;
            for (int j = 1; j <= 17; j++)
                ff[v][j] = ff[ff[v][j-1]][j-1];
            q.push(v);
        }
    }
}

int lca(int x, int y)
{
    if (d[x] > d[y]) swap(x, y);
    for (int i = 17; i >= 0; i--)
    {
        if (d[ff[y][i]] < d[x]) continue;
        y = ff[y][i];
    }
    if (x == y) return x;
    for (int i = 17; i >= 0; i--)
        if (ff[x][i] != ff[y][i]) {x = ff[x][i]; y = ff[y][i];}
    return ff[x][0];
}
inline int tdis(int x, int y)
{
    return d[x] + d[y] - ( d[lca(x, y)] << 1);
}
void getrt(int u, int f)
{
    siz[u] = 1; mp[u] = 0;
    for (int i = he[u]; i; i = ne[i])
    {
        int v = ver[i];
        if (v == f || vis[v]) continue;
        getrt(v, u);
        siz[u] += siz[v];
        if (siz[v] > mp[u]) mp[u] = siz[v];
    }
    mp[u] = _max(mp[u], sum-siz[u]);
    if (mp[u] < mp[rt]) rt = u;
}
int rt_w;
void getdis(int u, int f)
{
    insert( root[rt_w], dis[u], val[u]); 
    insert( root[rt_w + n], tdis(fa[rt_w], u), val[u]);
    for (int i = he[u]; i; i = ne[i])
    {
        int v = ver[i];
        if (v == f || vis[v]) continue;
        dis[v] = dis[u] + 1;
        getdis(v, u);
    }
}
void solve(int u)
{
    for (int i = he[u]; i; i = ne[i])
    {
        int v = ver[i];
        if (vis[v]) continue;
        dis[v] = 1;
        rt_w = u;
        getdis(v, u);//统计v子树的所有节点到v的距离
    }
    insert( root[u], 0, val[u] );
    insert( root[u + n], abs(d[u] - d[fa[u]]), val[u]);
}

void divide(int u)
{
    vis[u] = 1;
    solve(u);
    for (int i = he[u]; i; i = ne[i])
    {
        int v = ver[i];
        if(vis[v]) continue;
        mp[rt=0] = sum = siz[v];
        getrt(v, 0);
        fa[rt] = u;
        divide(rt);
    }
}
int mask(int x, int k)
{
    int ans = 0;
    for (int c = x; c; c = fa[c])
    {
        int g = tdis(x, c);
        if (k - g >= 0)
            ans +=  ask( root[c], 0,  k- g);
        int cc;
        if(fa[c] &&  k - (cc = tdis(x, fa[c]) ) >= 0)
        {
            ans -=  ask( root[c + n], 0, k- cc);
        }
    }
    return ans;
}
void mchange(int x, int k)
{
    int g = -val[x] + k;
    val[x] = k;
    for (int c = x; c; c = fa[c])
    {
        insert( root[c], tdis(x, c), g);
        if (fa[c])
             insert( root[c + n], tdis(x, fa[c]), g);
    }
    return;
}
inline int read()
{
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
int main()
{

    n = read(); m = read();
    for (int i = 1; i <= n; i++)
        val[i] = read();
    for (int i = 1; i < n; i++)
    {
        int x, y;
        x =read(); y =read();
        add(x, y); add(y, x);
    }
    
    bfs();
    mp[0] = sum = n;
    getrt(1, 0);
    divide(rt);
    int la = 0;
    while(m--)
    {
        int op, x, k; scanf("%d%d%d", &op, &x, &k);
        x ^= la, k ^= la;
        if (op == 0)
            printf("%d\n", la = mask(x, k));
        else mchange(x, k);
    }
    return 0;
}
##### 例二 P2056 [ZJOI2007]捉迷藏

求最远的黑点对。显然，如果没有修改，这就是个模板点分治，但是现在有修改，就必须用动态点分治。我们现在先考虑不修改的情况，显然，只要进行一遍点分治即可。我们按照重心顺序，分别统计每个点子树内的贡献。然后答案即为每个点的贡献的最大值。而现在考虑带修。我们不妨先把每个点的贡献先存起来。为x点的贡献。考虑修改x，我们发现，只有x和x的祖先的ans值发生了改变，所有我们知道：每次修改我们都暴力跳祖先。修改祖先的值。这时我们考虑这三个数据结构（数据集合）：

1、A, 这个维护的是数字的可重集合，即所有点贡献值的集合，这个数据结构要满足：每次查询可以快速的插入一个值、删除一个值，或者得到最大值。
2、B[x]，这个表示x点每个孩子的离x最远的黑点的距离的可重集合。这个数据结构要满足：每次查询可以快速的插入一个值、删除一个值，或者得到最大值和次大值。
3、C[x], 这个表示x点子树中所有黑点离fa[x]的距离的可重集合，这个数据结构要满足：每次查询可以快速的插入一个值、删除一个值，或者得到最大值。

这3个数据结构有个啥子用？试想我们把一个节点x的灯关上（把这个节点变成黑点），则我们就执行一下操作：

1、令，并在B[x]中插入0，（自己是一个黑点，即在x的子树中可以从某点到x形成一个黑点对）
2、如果x为根节点，停止，否则，执行以下操作：
--让A删除（B[fa[x]]的最大值+B[fa[x]]的次大值）
--让B[fa[x]]删除C[x]中的最大值。
--在C[x]插入dis（x0，fa[x]），
--让B[fa[x]]插入C[x]中的最大值。
--让A插入（B[fa[x]]的最大值+B[fa[x]]的次大值）
-- 返回2

显然，我们正确维护了三个数据结构，对于删除同同理，最终答案为A的最大值。

那么这三个奇怪的数据结构要怎么写呢，——它们和大根堆及其类似，但是我们必须让他们可以删除特定的数值。我们可以对大根堆加以改造，对于一个大根堆，维护两个priority_queue，X和Y。一个是大根堆，另一个是删除队列。对于插入操作，我们直接在X中维护，对于删除，我们把要删除的值插入到Y中。我们每次去最大值，要比对X和Y的堆顶，如果相同，就同时pop。直到X和Y的堆顶不一样或者Y为空。

下面是ac代码，

一共两份，第一份：使用上述方式写的不开O2。70point，开O2可以过。

第二个：我在看题解之前写的muliset，不开O2。90point，开O2 仍然是90piont（快哭了。）

by the way，似乎洛谷所有的题解，不开O2都是70point。（心里顿时平衡了许多

第一份（priority_queue）： 

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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
// % everyone
#include<cstdio>
#include<iostream>
#include<cstring>
#include <map>
#include <queue>
#include <set>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <bitset>
#include <array>
#include <cctype>
#include <time.h>


void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); }
void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); }
void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; }
template <typename T>
bool bacmp(const T & a, const T & b) { return a > b; }
template <typename T>
bool pecmp(const T & a, const T & b) { return a < b; }

#define ll long long
#define ull unsigned ll
#define _min(x, y) ((x)>(y)?(y):(x))
#define _max(x, y) ((x)>(y)?(x):(y))
#define max3(x, y, z) ( max( (x), max( (y), (z) ) ) )
#define min3(x, y, z) ( min( (x), min( (y), (z) ) ) )
#define pr(x, y) (make_pair((x), (y)))
#define pb(x) push_back(x)
using namespace std;
const int N = 1e5+5;
int ver[N<<1], he[N], ne[N<<1];
int tot, rt, sum;
int siz[N], dis[N], mp[N];
bool vis[N]; int fa[N];
bool val[N];
int n, m;
struct que
{
    priority_queue<int> x,y;
    inline void push(int a){x.push(a);}
    inline void del(int a){y.push(a);}
    inline int top(){while(y.size()&&x.top()==y.top())x.pop(),y.pop();return x.top();}
    inline int size(){return x.size()-y.size();}
    inline void pop(){while(y.size()&&x.top()==y.top())x.pop(),y.pop();x.pop();}
    inline int sectop(){int a=top();pop();int b=top();push(a);return b;}
} A,B[N],C[N];
inline void pusha(int x)
{
    if(B[x].size()>=2) A.push(B[x].top()+B[x].sectop());
}
inline void dela(int x)
{
    if(B[x].size()>=2) A.del(B[x].top()+B[x].sectop());
}
void add(int x, int y)
{
    ver[++tot] = y;
    ne[tot] = he[x];
    he[x] = tot;
}
int ff[N][18];
int d[N];
void bfs()
{
    queue<int> q;
    d[1] = 1;
    q.push(1);
    while(q.size())
    {
        int te = q.front();
        q.pop();
        for (int i = he[te]; i; i = ne[i])
        {
            int v = ver[i];
            if (d[v]) continue;
            d[v] = d[te] + 1;
            ff[v][0] = te;
            for (int j = 1; j <= 17; j++)
                ff[v][j] = ff[ff[v][j-1]][j-1];
            q.push(v);
        }
    }
}
int lca(int x, int y)
{
    if (d[x] > d[y]) swap(x, y);
    for (int i = 17; i >= 0; i--)
    {
        if (d[ff[y][i]] < d[x]) continue;
        y = ff[y][i];
    }
    if (x == y) return x;
    for (int i = 17; i >= 0; i--)
        if (ff[x][i] != ff[y][i]) {x = ff[x][i]; y = ff[y][i];}
    return ff[x][0];
}
inline int tdis(int x, int y)
{
    return d[x] + d[y] - ( d[lca(x, y)] << 1);
}
void getrt(int u, int f)
{
    siz[u] = 1; mp[u] = 0;
    for (int i = he[u]; i; i = ne[i])
    {
        int v = ver[i];
        if (v == f || vis[v]) continue;
        getrt(v, u);
        siz[u] += siz[v];
        if (siz[v] > mp[u]) mp[u] = siz[v];
    }
    mp[u] = _max(mp[u], sum-siz[u]);
    if (mp[u] < mp[rt]) rt = u;
}
int rt_w, rt_v;
int con[N];
int anss[N];
void sol(int x, int f)
{
    C[rt_v].push(tdis(x, rt_w));
    for (int i = he[x]; i; i = ne[i])
    {
        int y= ver[i];
        if (y == f || vis[y]) continue;
        sol(y, x);
    }
}
void divide(int u)
{
    vis[u] = 1;
    B[u].push(0);
    int pp = 0;
    for (int i = he[u]; i; i = ne[i])
    {
        int v = ver[i];
        if(vis[v]) continue;
        mp[rt=0] = sum = siz[v];
        getrt(v, 0);
        con[rt] = pp;
        fa[rt] = u;
        rt_v = rt;
        rt_w = u;
        sol(rt, 0);
        if (C[rt].size())
            B[u].push(C[rt].top());
        divide(rt);
        pp++;
    }
    pusha(u);
}

void ins(int x)
{
    dela(x);
    B[x].push(0);
    pusha(x);
    for(int i=x; fa[i]; i=fa[i])
    {
        dela(fa[i]);
        if(C[i].size())B[fa[i]].del(C[i].top());
        C[i].push(tdis(x,fa[i]));
        B[fa[i]].push(C[i].top());
        pusha(fa[i]);
    }
}
void del(int x)
{
    dela(x);
    B[x].del(0);
    pusha(x);
    for (int i = x; fa[i]; i = fa[i])
    {
        dela(fa[i]);
        B[fa[i]].del(C[i].top());
        C[i].del(tdis(x,fa[i]));
        if (C[i].size()) B[fa[i]].push(C[i].top());
        pusha(fa[i]);
    }
}
int np = 0;
void mchange(int x)
{
    if (val[x] == 0)
    {
        val[x] = 1;
        np--;
        del(x);
    }
    else
    {
        val[x] = 0;
        np++;
        ins(x);
    }
    return;
}
inline int read(){
    int s=0,w=1;
    char ch= getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int main()
{
    int n; n = read();
    for (int i = 1; i < n; i++)
    {
        int x, y; x = read(); y = read();
        add(x, y); add(y, x);
    }
    bfs();
    mp[0] = sum = n;
    getrt(1, 0);
    divide(rt);
    np = n;
    int m; m =read();
    while(m--)
    {
        char op[3]; int x;
        scanf("%s", op);
        if (op[0] == 'G')
        {
            if (np >= 2)
                printf("%d\n", A.top() );
            else printf("%d\n", np - 1);
        }
        else
        {
            x = read();
            mchange(x);
        }
    }
    return 0;
}
第二份：（muliset） 
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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
// % everyone
#include<cstdio>
#include<iostream>
#include<cstring>
#include <map>
#include <queue>
#include <set>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <bitset>
#include <array>
#include <cctype>
#include <time.h>


void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); }
void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); }
void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; }
template <typename T>
bool bacmp(const T & a, const T & b) { return a > b; }
template <typename T>
bool pecmp(const T & a, const T & b) { return a < b; }

#define ll long long
#define ull unsigned ll
#define _min(x, y) ((x)>(y)?(y):(x))
#define _max(x, y) ((x)>(y)?(x):(y))
#define max3(x, y, z) ( max( (x), max( (y), (z) ) ) )
#define min3(x, y, z) ( min( (x), min( (y), (z) ) ) )
#define pr(x, y) (make_pair((x), (y)))
#define pb(x) push_back(x)
using namespace std;
const int N = 1e5+5;
int ver[N<<1], he[N], ne[N<<1];
int tot, rt, sum;
int siz[N], dis[N], mp[N];
bool vis[N]; int fa[N];
bool val[N];
int n, m;
multiset<int> ans;
multiset<int> fans[N];
vector< multiset<int> > fsans[N];
void add(int x, int y)
{
    ver[++tot] = y;
    ne[tot] = he[x];
    he[x] = tot;
}
int ff[N][18];
int d[N];
void bfs()
{
    queue<int> q;
    d[1] = 1;
    q.push(1);
    while(q.size())
    {
        int te = q.front();
        q.pop();
        for (int i = he[te]; i; i = ne[i])
        {
            int v = ver[i];
            if (d[v]) continue;
            d[v] = d[te] + 1;
            ff[v][0] = te;
            for (int j = 1; j <= 17; j++)
                ff[v][j] = ff[ff[v][j-1]][j-1];
            q.push(v);
        }
    }
}

int lca(int x, int y)
{
    if (d[x] > d[y]) swap(x, y);
    for (int i = 17; i >= 0; i--)
    {
        if (d[ff[y][i]] < d[x]) continue;
        y = ff[y][i];
    }
    if (x == y) return x;
    for (int i = 17; i >= 0; i--)
        if (ff[x][i] != ff[y][i]) {x = ff[x][i]; y = ff[y][i];}
    return ff[x][0];
}
inline int tdis(int x, int y)
{
    return d[x] + d[y] - ( d[lca(x, y)] << 1);
}
void getrt(int u, int f)
{
    siz[u] = 1; mp[u] = 0;
    for (int i = he[u]; i; i = ne[i])
    {
        int v = ver[i];
        if (v == f || vis[v]) continue;
        getrt(v, u);
        siz[u] += siz[v];
        if (siz[v] > mp[u]) mp[u] = siz[v];
    }
    mp[u] = _max(mp[u], sum-siz[u]);
    if (mp[u] < mp[rt]) rt = u;
}
int rt_w;
int con[N];
int anss[N];
void divide(int u)
{
    vis[u] = 1;
    int pp = 0;
    for (int i = he[u]; i; i = ne[i])
    {
        int v = ver[i];
        if(vis[v]) continue;
        mp[rt=0] = sum = siz[v];
        getrt(v, 0);
        con[rt] = pp;
        fa[rt] = u;
        divide(rt);
        fsans[u].pb(multiset<int>());
        pp++;
    }
}
int getn(int x)
{
    if (fans[x].size() <= 1) return 0;
    auto it = fans[x].rbegin();
    int g = *it; it++;
    return g + *it;
}
void del(int x)
{
    if (anss[x] )
        ans.erase(ans.lower_bound(anss[x]));
    fans[x].erase(fans[x].lower_bound(0));
    if (anss[x])
        anss[x] = getn(x);
    ans.insert(anss[x]);
    for (int son = x; fa[son];  son = fa[son])
    {
        int c = fa[son];
        int f = tdis(x, c);
        int gg = con[son];
        if (fsans[c][gg].size() && f != *fsans[c][gg].rbegin())
        {
            fsans[c][gg].erase(fsans[c][gg].lower_bound(f));
            continue;
        }
        int mx = *fsans[c][gg].rbegin();
        fans[c].erase(fans[c].lower_bound(mx));
        fsans[c][gg].erase(fsans[c][gg].lower_bound(f));
        if (fsans[c][gg].size())
        {
            fans[c].insert(*fsans[c][gg].rbegin());
        }
        int fs = anss[c];
        anss[c] = getn(c);
        if (fs != anss[c])
        {
            if(fs)
                ans.erase(ans.lower_bound(fs));
            if (anss[c])
                ans.insert(anss[c]);
        }
    }
}
void ins(int x)
{
    if (anss[x])
        ans.erase(ans.lower_bound(anss[x]));    
    fans[x].insert(0);
    anss[x] = getn(x);
    if (anss[x])
        ans.insert(anss[x]);
    for (int son = x; fa[son];  son = fa[son])
    {
        int c = fa[son];
        int f = tdis(x, c);
        int gg = con[son];
        if (fsans[c][gg].size() && f <= *fsans[c][gg].rbegin())
        {
            fsans[c][gg].insert(f);
            continue;
        }
        if (fsans[c][gg].size())
        {
            int mx = *fsans[c][gg].rbegin();
            fans[c].erase(fans[c].lower_bound(mx));
        }
        fsans[c][gg].insert(f);
        fans[c].insert(*fsans[c][gg].rbegin());
        int fs = anss[c];
        anss[c] = getn(c);
        if (fs != anss[c])
        {
            if(fs)
                ans.erase(ans.lower_bound(fs));
            if (anss[c])
                ans.insert(anss[c]);
        }
    }
}
int np = 0;
void mchange(int x)
{
    if (val[x] == 1)
    {
        val[x] = 0;
        np--;
        del(x);
    }
    else
    {
        val[x] = 1;
        np++;
        ins(x);
    }
    return;
}
inline int read(){
    int s=0,w=1;
    char ch= getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int main()
{
    int n; n = read();
    for (int i = 1; i < n; i++)
    {
        int x, y; x = read(); y = read();
        add(x, y); add(y, x);
    }
    bfs();
    mp[0] = sum = n;
    getrt(1, 0);
    divide(rt);
    for (int i = 1; i <= n; i++) mchange(i);
    int m; m =read();
    while(m--)
    {
        char op[3]; int x;
        scanf("%s", op);
        if (op[0] == 'G')
        {
            if (np >= 2)
                printf("%d\n", *ans.rbegin() );
            else printf("%d\n", np - 1);
        }
        else
        {
            x = read();
            mchange(x);
        }
    }
    return 0;
}

本文作者：Kalzn
本文链接：http://kalzncc.github.io/2020/09/26/108759856/
版权声明：除文章中特别注明外，本站所有文章采用 CC BY 3.0 CN 协议进行许可
即在署明文章作者及来源的情况下，您可以将本文用于包括商业目在内的任何用途。
除此之外，本文不做正确性担保，本人不对产生的问题负责。
×