[SHOI2005]树的双中心

快来打我* 2021-12-03 20:25 160阅读 0赞

题目链接：[Click here][]

## Solution: ##

首先我们要知道，选择两个点\\(A,B\\)，必定存在一条边，割掉这条边，两个集合分别归\\(A,B\\)管

再结合题目，我们就得到了一个暴力的\\(n^2\\)做法：枚举个每条边，分别对两棵树求带权重心，更新答案

但这显然是过不了这道题的，考虑对求带权重心的过程进行优化：

设\\(d(x)\\)为\\(x\\)所在集合内所有点到他的距离之和，\\(sz(x)\\)表示以\\(x\\)为根的子树的大小，我们可以得到：  
\\\[ d(v)=d(u)+sz(rt)-sz(v)-sz(v) \\\]  
其中\\(u=fa(v)\\)，则若一个点\\(v\\)比\\(u\\)更优，即\\(d(v)<d(u)\\)，可以得到\\(2\\times sz(v)>sz(rt)\\)

显而易见的是，对于每一个\\(u\\)，符合条件的\\(v\\)最多只有一个，则算法得到了很大的优化

我们对每一个点预处理出一个重儿子和次重儿子，处理出次重儿子的原因是割边后\\(sz\\)会发生变化

然后在更新过程中只要考虑当前重儿子是否满足条件即可，最坏时间复杂度\\(O(n \\times dep)\\)

## Code: ##

#include<bits/stdc++.h> using namespace std; const int N=5e4+1; int n,ans,cnt,no,head[N],f[N],a[N]; int fa[N],sz[N],son[N],nson[N],dep[N]; struct Edge{int nxt,to;}edge[N<<1]; void ins(int x,int y){ edge[++cnt].nxt=head[x]; edge[cnt].to=y;head[x]=cnt; } void dfs(int x,int fat){ sz[x]=a[x];fa[x]=fat; for(int i=head[x];i;i=edge[i].nxt){ int y=edge[i].to; if(y==fa[x]) continue; dep[y]=dep[x]+1; dfs(y,x);sz[x]+=sz[y]; if(sz[y]>sz[nson[x]]){ nson[x]=y; if(sz[son[x]]<sz[nson[x]]) swap(son[x],nson[x]); }f[x]+=f[y]+sz[y]; } } int calc(int x,int val,int u){ int y=son[x];if(son[x]==no||sz[nson[x]]>sz[son[x]]) y=nson[x]; if(y&&(sz[y]<<1)>sz[u]) return calc(y,val+sz[u]-(sz[y]<<1),u);return val; } void cut(){ for(int i=1;i<=cnt;i+=2){ int x=edge[i].to,y=edge[i+1].to;if(fa[y]!=x) swap(x,y); no=y;for(int u=x;u;u=fa[u]) sz[u]-=sz[y]; int u1=calc(1,f[1]-f[y]-sz[y]*dep[y],1); int u2=calc(y,f[y],y);ans=min(ans,u1+u2); for(int u=x;u;u=fa[u]) sz[u]+=sz[y]; } } int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } int main(){ n=read();ans=2147483647; for(int i=1;i<n;i++){ int x=read(),y=read(); ins(x,y),ins(y,x); } for(int i=1;i<=n;i++) a[i]=read(); dfs(1,0);cut();printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/NLDQY/p/11185345.html

[Click here]: https://www.luogu.org/problemnew/show/P2726