LUOGU P2986 [USACO10MAR]伟大的奶牛聚集Great Cow Gat…

解题思路

首先第一遍dfs预处理出每个点的子树的siz，然后可以处理出放在根节点的答案，然后递推可得其他答案，递推方程 sum[u]=sum[x]-(val[i]*siz[u])+(siz[1]-siz[u])*val[i]

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

using namespace std;

const int MAXN = 100005;

typedef long long LL;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

LL ans,sum[MAXN],all[MAXN];

int siz[MAXN],n,head[MAXN],cnt,to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1];

inline void add(int bg,int ed,int w){

	to[++cnt]=ed,nxt[cnt]=head[bg],val[cnt]=w,head[bg]=cnt;

}

void dfs1(int x,int fa,int d){

	all[x]=(LL)siz[x]*d;

	for(register int i=head[x];i;i=nxt[i]){

		int u=to[i];if(u==fa) continue;

		dfs1(u,x,d+val[i]);

		siz[x]+=siz[u];all[x]+=all[u];

	}

}

void dfs2(int x,int fa){

	for(register int i=head[x];i;i=nxt[i]){

		int u=to[i];if(u==fa) continue;

		sum[u]=sum[x]-((LL)siz[u]*val[i])+(LL)(siz[1]-siz[u])*val[i];

		ans=min(ans,sum[u]);

		dfs2(u,x);

	}

}

int main(){

	n=rd();int x,y,z;

	for(int i=1;i<=n;i++) siz[i]=rd();

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

		x=rd(),y=rd(),z=rd();

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

	}

	dfs1(1,0,0);ans=sum[1]=all[1];dfs2(1,0);

	cout<<ans<<endl;

	return 0;

}

巴特西

LUOGU P2986 [USACO10MAR]伟大的奶牛聚集Great Cow Gat…

解题思路

代码

最新文章

热门文章