BZOJ3302: [Shoi2005]树的双中心

BZOJ3302: [Shoi2005]树的双中心

https://lydsy.com/JudgeOnline/problem.php?id=3302

分析:

• 朴素算法 : 枚举边，然后在两个连通块内部找到带权重心计算答案。
• 然后我们发现在内部找重心是方向唯一，因此可以预处理出来这个点向下走的最优儿子和次优儿子。
• 然后每次从上往下找重心即可。
• 时间复杂度\(O(n\times dep)\)。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

typedef long long ll;

#define N 50050

#define ls ch[x][0]

#define rs ch[x][1]

int head[N],to[N<<1],nxt[N<<1],cnt,n,ch[N][2],dep[N];

ll w[N],sw[N],sd[N],ans;

inline void add(int u,int v) {

	to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;

}

void d1(int x,int y) {

	int i; sw[x]=w[x];

	for(i=head[x];i;i=nxt[i]) if(to[i]!=y) {

		dep[to[i]]=dep[x]+1;

		d1(to[i],x); sw[x]+=sw[to[i]]; sd[x]+=sd[to[i]]+sw[to[i]];

		if(sd[to[i]]>sd[ls]) rs=ls,ls=to[i];

		else if(sd[to[i]]>sd[rs]) rs=to[i];

	}

}

ll now,tot,sz;

int ins[N];

ll calc(int x,int y) {

	ll sy=sw[y]-(ins[y])*sz;

	return now-sy+tot-sy;

}

int rt;

void d3(int x) {

	ll t1=calc(x,ls),t2=calc(x,rs);

	if(t1<t2) {if(t1<now)now=t1,d3(ch[x][0]);}

	else if(t2<now) now=t2,d3(ch[x][1]);

}

void d2(int x,int y) {

	int i;

	ins[x]=1;

	for(i=head[x];i;i=nxt[i]) if(to[i]!=y) {

		ins[to[i]]=1;

		ll tmp=0;

		rt=x;

		tot=sw[to[i]]; sz=0; now=sd[to[i]]; d3(to[i]); tmp+=now;

		tot=sw[1]-sw[to[i]]; sz=sw[to[i]]; now=sd[1]-sd[to[i]]-dep[to[i]]*sw[to[i]]; d3(1); tmp+=now;

		ans=min(ans,tmp);

		d2(to[i],x);

	}

	ins[x]=0;

}

int main() {

	scanf("%d",&n);

	int i,x,y;

	for(i=1;i<n;i++) {

		scanf("%d%d",&x,&y);

		add(x,y); add(y,x);

	}

	for(i=1;i<=n;i++) scanf("%lld",&w[i]);

	sd[0]=0;

	d1(1,0);

	ans=sd[1];

	d2(1,0);

	printf("%lld\n",ans);

}