解题：USACO10MAR Great Cow Gather

可以水水换根的，不过我是另一种做法：(按点权)找重心，事实上这是重心的一个性质

考虑换根的这个过程，当我们把点放在重心时，我们移动这个点有两种情况：

1.移动到最大的那个子树里

可以发现这个最大的子树的$size$不可能超过其余子树的$size$之和(最多是有两个重心的时候等于其他子树的$size$之和)，不然你找的是假重心

2.移动到其他的子树里

显然这样只会让答案变差

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 long long dis[N],val[*N],num[N],maxx[N],siz[N];

 int p[N],noww[*N],goal[*N],vis[N];

 long long ans,tot,t3,maxn=1e16;

 int n,c,t1,t2,cnt;

 void link(int f,int t,long long v)

 {

     noww[++cnt]=p[f],p[f]=cnt;

     goal[cnt]=t,val[cnt]=v;

 }

 void MARK(int nde,int fth)

 {

     siz[nde]=num[nde];

     for(int i=p[nde];i;i=noww[i])

         if(goal[i]!=fth)

         {

             MARK(goal[i],nde);

             siz[nde]+=siz[goal[i]];

             maxx[nde]=max(maxx[nde],siz[goal[i]]);

         }

     maxx[nde]=max(maxx[nde],tot-siz[nde]);

     if(maxx[nde]<maxn) maxn=maxx[nde],c=nde;

 }

 void DFS(int nde,int fth)

 {

     for(int i=p[nde];i;i=noww[i])

         if(goal[i]!=fth)

         {

             dis[goal[i]]=dis[nde]+val[i];

             DFS(goal[i],nde);

         }

 }

 int main()

 {

     scanf("%d",&n);

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

         scanf("%lld",&num[i]),tot+=num[i];

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

     {

         scanf("%d%d%lld",&t1,&t2,&t3);

         link(t1,t2,t3),link(t2,t1,t3);

     }

     c=; MARK(,); DFS(c,);

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

         ans+=dis[i]*num[i];

     printf("%lld",ans);

     return ;

 }

巴特西

解题：USACO10MAR Great Cow Gather

最新文章

热门文章