CSP2019 树的重心 题解

$\text{Descripton}$

给定一棵树,求出删除每一条边后分裂出的两个子树的重心编号和。

$\text{Solution}$

考虑一个最显然的暴力,枚举删除的边,暴力求两个子树的重心,这样是 $O(n^2)$ 的。

上面的做法可以通过倍增优化至 $O(n\log n)$,但我太菜了不会。

考虑求每个点对答案的贡献。

我们先以原树的一个重心为根,这样可以有比较好的性质。

记 $x$ 为我们当前考虑贡献的节点,$s_i$ 表示以 $i$ 为根的子树大小,$S$ 为删边后不包含 $x$ 的新树大小,$g_i$ 表示以 $i$ 的重儿子为根的子树大小。

先考虑 $x$ 不是根的情况。

我们发现,若要使 $x$ 成为重心,删的边不可能在 $x$ 的子树里。为什么?考虑删除根(注意是重心)后 $x$ 所在的子树大小不超过 $\lfloor\dfrac{n}{2}\rfloor$,故其它子树大小的和至少是 $\lfloor\dfrac{n}{2}\rfloor$,发现其它子树会和根一起作为 $x$ 所在的新树中 $x$ 的一棵子树,显然它的大小超过了新树大小的一半,不符合定义。

根据重心的定义,还可以有:

事实上由于整除的性质,我们整理得到:

从而将问题转换为了,找到这个范围内 $S$ 的个数,同时满足删边不在 $x$ 的子树内。考虑求出满足前者的个数,然后减去满足前者但不满足后者的个数。满足前者的个数,实际上只需开一个权值树状数组,动态维护对于 $x$ 来说 的 $S$ 值。为什么这么说呢?因为同样是删除一条边,对于这条边以下的点,它们的 $S$ 实际上是包含根节点的新树,对于其它的点,他们的 $S$ 实际上是不包含根节点的新树。在深搜过程中,一个节点处理完马上就是它的子树内的点,利用这个去动态维护就好。

然后考虑满足前者但不满足后者的个数。线段树合并固然可做,但是引用某队爷的话:

用线段树合并小题大作了吧。

嗯,考虑到刚进入一个节点和准备离开这个节点时,我们多处理了以这个点为根的子树的信息,利用这个作差即可,考虑到我们只要删的边在 $x$ 的子树内,故 $S$ 实际上只能是不包含根节点的新树,这就十分简单了。

还有 $x$ 为根的情况没有解决呢。发现我们只需注意根的重儿子 $u$ 和次重儿子 $v$,考虑以下两种情况:

若删除的边不在以 $u$ 为根的子树中,那么只需满足(此处借由上文整除的性质并且整理过式子):

若删除的边在以 $u$ 为根的子树中,考虑两条限制:

注意到前面是个负数,无意义,那么其实就是:

这些可以把每个点枚举过去解决。

$\text{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
#include<bits/stdc++.h>
#define REG register
#define MAXN 300005
#define LL long long
#define FORE(i,now) for(REG int i=head[now];i;i=ed[i].nxt)
using namespace std;
inline int read(){
REG int x(0);
REG char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x*10)+(c^48),c=getchar();
return x;
}
inline void Swap(int& a,int& b){int t=a;a=b,b=t;}

int T,n;
struct Edge{
int v,nxt;
}ed[MAXN<<1];
int head[MAXN],cnt;
inline void adde(int u,int v){
ed[++cnt]=(Edge){v,head[u]};
head[u]=cnt;
}
inline void add(int u,int v){
adde(u,v),adde(v,u);
}

int s[MAXN],g[MAXN],Dir[MAXN],rt,Fir,Sec;
LL ans;

struct t{
int c[MAXN];
inline void Clear(){memset(c,0,sizeof c);}
inline void Upd(int pos,int k){++pos;for(;pos<=n+1;pos+=pos&-pos)c[pos]+=k;}
inline int Ask(int pos){++pos;int ans=0;for(;pos;pos-=pos&-pos)ans+=c[pos];return ans;}
}c1,c2;

void Find_rt(int now,int fa){
s[now]=1,g[now]=0;
FORE(i,now){
int v=ed[i].v;
if(v==fa) continue;
Find_rt(v,now);
s[now]+=s[v];
if(s[v]>g[now]) g[now]=s[v];
}
if(g[now]<=(n>>1)&&n-s[now]<=(n>>1)) rt=now;
}

void ReBuild(int now,int fa){
s[now]=1,g[now]=0;
FORE(i,now){
int v=ed[i].v;
if(v==fa) continue;
ReBuild(v,now);
s[now]+=s[v];
if(s[v]>g[now]) g[now]=s[v];
}
}

void Solve(int now,int fa){
c1.Upd(s[now],-1),c1.Upd(n-s[now],1),c2.Upd(s[now],1);
Dir[now]|=Dir[fa];
if(now^rt){
ans+=(LL)now*(c1.Ask(n-2*g[now])-c1.Ask(n-2*s[now]-1));
ans+=(LL)now*(c2.Ask(n-2*g[now])-c2.Ask(n-2*s[now]-1));
ans+=(LL)rt*(s[now]<=n-2*s[Dir[now]?Sec:Fir]);
}
FORE(i,now){
int v=ed[i].v;
if(v==fa) continue;
Solve(v,now);
}
if(now^rt)
ans-=(LL)now*(c2.Ask(n-2*g[now])-c2.Ask(n-2*s[now]-1));
c1.Upd(s[now],1),c1.Upd(n-s[now],-1);

}

void Init(){
memset(head,0,sizeof head);
memset(Dir,0,sizeof Dir);
cnt=0;
c1.Clear(),c2.Clear();
Fir=Sec=ans=0;
n=read();
for(REG int i=1;i<n;++i) add(read(),read());
Find_rt(1,0);
ReBuild(rt,0);
FORE(i,rt){
int v=ed[i].v;
if(s[v]>s[Sec]) Sec=v;
if(s[Sec]>s[Fir]) Swap(Fir,Sec);
}
for(REG int i=1;i<=n;++i) c1.Upd(s[i],1);
Dir[Fir]=1;
Solve(rt,0);
}

int main(){
T=read();
while(T--){
Init();
printf("%lld\n",ans);
}
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×