Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

csp-2019 树的重心

Posted on

不知道性质的话这题就只有暴力分了。

Solution

树的重心的性质：

  1. 一棵树如果有两个重心，这两个重心一定是相邻的
  2. 一棵树的重心一定在根节点所在的重链上
  3. 一棵树的重心一定是以该树根节点重儿子为根的子树的重心的祖先

知道了性质之后回过头来再次审视题目：首先预处理出这棵树每个节点的重儿子，次重儿子，然后使用换根$dp$开始从$1$根节点开始逐渐向每一颗子树转移，对于每一颗子树我们使用倍增的方式找重心，然后对于每一个找到的点，判断其父亲节点，重儿子节点和本身节点是否为重心，然后统计进入答案。

具体怎么样换根：对于任意节点$x$，现在要计算断开它的子树$j$时两颗树的贡献，不难发现$j$的子树没有动，直接倍增找即可，现在来观察新子树$x$，此时新子树的大小显然应该为$sz[1] - sz[j]$，而$x$新增的子树显然就是$father[x]$只需判断$father[x]$是否会成为$x$的新的重儿子然后倍增跳即可。

注：对于$x$被断开的子树$j$，如果其不是$x$的重儿子，那么$x$的新重儿子就是在$father[x]$和$heavy-son[x]$中选择，否则就应该在$second-heavy-son[x]$和$father[x]$中选择。

Code

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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res), putchar('\n');
}
const int N = 3e5 + 5;
int n;
int idx;
int e[N << 1], ne[N << 1], h[N];
inline void add(int x, int y)
{
    idx ++;
    e[idx] = y, ne[idx] = h[x], h[x] = idx;
}
int son[N], son2[N], f[N], fa[N], sz[N], tr[N][19];
int sz2[N], son3[N];
void dfs(int x, int y)
{
    sz[x] = 1, fa[x] = y;
    for(int i = h[x], j; ~i;i = ne[i])
    {
        j = e[i];
        if(j == y) continue;
        dfs(j, x);
        sz[x] += sz[j];
        if(sz[j] > sz[son[x]]) son2[x] = son[x], son[x] = j;
        else if(sz[j] > sz[son2[x]]) son2[x] = j;
    }   
    tr[x][0] = son[x];
    for(int i = 1;i <= 17;i ++)
        tr[x][i] = tr[tr[x][i - 1]][i - 1];
}
LL ans;
inline int check(int x, int sum)
{
    return x * (max(sz2[son3[x]], sum - sz2[x]) <= sum / 2);
}
void dfs2(int x, int y)
{
    for(int i = h[x], j; ~i;i = ne[i])
    {
        j = e[i];
        if(j == y) continue;
        sz2[x] = sz[1] - sz[j];
        f[j] = f[x] = 0;
        if(son[x] == j) son3[x] = son2[x];
        else son3[x] = son[x];
        if(sz2[y] > sz2[son3[x]]) son3[x] = y;
        tr[x][0] = son3[x];
        for(int k = 1;k <= 17;k ++) tr[x][k] = tr[tr[x][k - 1]][k - 1];
        int now = x;
        for(int k = 17;k >= 0;k --)
            if(sz2[x] - sz2[tr[now][k]] <= sz2[x] / 2)
                now = tr[now][k];
        ans += check(son3[now], sz2[x]) + check(now, sz2[x]) + check(f[now], sz2[x]);
        now = j;
        for(int k = 17;k >= 0;k --)
            if(sz2[j] - sz2[tr[now][k]] <= sz2[j] / 2)
                now = tr[now][k];
        ans += check(son3[now], sz2[j]) + check(now, sz2[j]) + check(f[now], sz2[j]);
        f[x] = j;
        dfs2(j, x);
    }
    son3[x] = tr[x][0] = son[x];
    f[x] = fa[x];
    for(int j = 1;j <= 17;j ++) tr[x][j] = tr[tr[x][j - 1]][j - 1];
    sz2[x] = sz[x];
}
inline void work()
{
    memset(h, -1, sizeof(h));
    memset(son, 0, sizeof(f));
    memset(f, 0, sizeof(f));
    memset(fa, 0, sizeof(fa));
    idx = ans = 0;
    read(n);
    for(int i = 1, o, u;i < n;i ++) read(o, u), add(o, u), add(u, o);
    dfs(1, 0);
    memcpy(sz2, sz, sizeof(sz2));
    memcpy(son3, son, sizeof(son3));
    memcpy(f, fa, sizeof(f));
    dfs2(1, 0);
    write(ans);
} 
int main()
{
    int T;
    read(T);
    while(T --) work();
    return 0;
}
/*
input
1
7
1 6
2 4
5 3
3 7
6 4
4 7
output
73
*/