题意
(T) 组数据 ((1 le T le 5)), 每次给定一棵 (n) 个点的树 ((1 le n le 299995)).
设 (E) 为树的边集, (V'_x, V'_y) 分别为删去边 ((x,y)) 后 点 (x) 所在的点集和点 (y) 所在的点集.
求
思路
40 pts
暴力枚举每一条边, 求重心即可.
100 pts
做法 1
总的思路是从枚举边变为枚举点,
具体操作 :
枚举每一个点 (u), 对该点的每一棵子树都处理出 (w_i) 表示, 该子树内权值为 (i) 的边的个数,
这里边的权值定义为 : 以 (u) 为根节点时, 删去这条边后, 删掉的节点个数.
再分类讨论当前枚举到的子树是不是权值最大的子树, 找到一个区间 ([l,r]), 使删去的边的权值 (e_i in [l,r]) 时, 点 (u) 为新树的重心, 用树状数组区间求和即可.
问题在于, 我们每次要独立地获得每个子树的边的数量, 所以就要用到线段树合并或者主席树, 不然的话每次重新获取子树的边的复杂度会达到 (O(n^2)), 然后本人线段树合并与主席树都不会, 所以....
做法 2
总思路: 利用倍增优化找重心的过程.
突破口: 树的重心一定在根节点的重路径上.
证明:
定义 (son[u]) 为节点 (u) 的重儿子.
设该树的根节点为 (t), (v, u) 为该树上的两个节点, 且 (fa[v]=u), (v
ot = son[u]).
反证法: 假设 (v) 为以 (t) 为根节点的树重心,
则 $ sz[t]-sz[v] le frac{sz[t]}{2} $,
所以 $ sz[v] ge frac{sz[t]}{2} $.
设 (p), 满足 (fa[p]=u), 且 (p
ot = v),
则 (sz[p] le sz[u]-1-sz[v] le sz[u]-1-frac{sz[t]}{2} le sz[t]-1-frac{sz[t]}{2} le sz[v])
所以 (v) 为 (u) 的重儿子, 产生矛盾, 假设不成立,
得证.
具体做法:
设 (s[u][i]) 为从节点 (u) 沿着重路径往下跳 (2^i) 步后到达的点.
设 (t) 为当前树的根节点.
当 (sz[s[u][i]] > frac{sz[t]}{2}) 时, (u=s[u][i]),
不断往下跳, 直到找到第一个有可能成为重心的点, 然后判断这个点以及它的重儿子是不是重心 (因为一棵树最多只能由两个重心, 所以只需判断这两个点), 若是, 则加入答案中.
首先, 我们随便找一个点作为根节点, 那么这里我们默认选择 (1) 号点.
然后, 对于每一个节点, 我们枚举它连向子节点的每一条边, 然后分类讨论, 重新选择 (u) 的重儿子 (详见代码).
总时间复杂度 (O(nlog n))
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=299995+7;
const int L=20;
int T,n,sz[N],son[N][2],s[N][L+7];
ll ans;
int lst[N],nxt[2*N],to[2*N],tot;
void add(int x,int y){ nxt[++tot]=lst[x]; to[tot]=y; lst[x]=tot; }
void rfs(int u){
s[u][0]=son[u][0];
for(int i=1;i<=L;i++)
s[u][i]=s[s[u][i-1]][i-1];
}
void pre(int u,int fa){
for(int i=lst[u];i;i=nxt[i]){
int v=to[i];
if(v==fa) continue;
pre(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u][0]]){ son[u][1]=son[u][0]; son[u][0]=v; }
else if(sz[v]>sz[son[u][1]]) son[u][1]=v;
}
sz[u]++;
rfs(u);
}
void find(int u){
int t=u;
for(int i=L;i>=0;i--)
if(sz[s[u][i]]>sz[t]/2)
u=s[u][i];
if(sz[t]-sz[u]<=sz[t]/2) ans+=(ll)u;
u=s[u][0];
if(sz[t]-sz[u]<=sz[t]/2) ans+=(ll)u;
}
void run(int u,int fa){
int t1=son[u][0],t2=sz[u]; // 先备份
for(int i=lst[u];i;i=nxt[i]){
int v=to[i];
if(v==fa) continue;
if(v==t1) son[u][0]= sz[son[u][1]]>n-t2 ?son[u][1] :fa; // 重新选取 u 的重儿子.
else son[u][0]= sz[t1]>n-t2 ?t1 :fa;
sz[u]=n-sz[v];
rfs(u); // 记得把 son[u][i] 也更新一遍
find(u); find(v);
run(v,u);
}
son[u][0]=t1; // 还原
sz[u]=t2;
rfs(u); //更新
}
int main(){
// freopen("gc.in","r",stdin);
cin>>T;
while(T--){
scanf("%d",&n);
memset(lst,0,sizeof(lst));
memset(son,0,sizeof(son));
memset(sz,0,sizeof(sz));
tot=ans=0;
int x,y;
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
pre(1,0);
run(1,0);
printf("%lld
",ans);
}
return 0;
}