题解 P2986 【[USACO10MAR]伟大的奶牛聚集Great Cow Gat…】

· · 题解

考虑如果依次枚举每一个点作为集会的地点

使用DFS进行计算

然后再依次比较

时间复杂度O(n^2)

但是n的范围太大，显然会超时。

那么，我们应当如何优化？

先看看样例

通过一次O(n)的计算，很容易得出来

如果选择1号节点，答案就是17

既然O(n^2)的计算无法在时间内求解

那么是否可以递推出来呢？

显然是可以的。

观察如果已经知道1号节点所需的时间

那么，我们可以做如下假设：

① 所有的牛首先到达了1号节点

② 3号节点以及他子树上的节点都需要退回1->3的路径的长度

③ 除了3号节点以及他子树上的节点都需要前进1->3的路径的长度

通过上面的三条东西，我们就可以从任意一个父节点推出子节点的时间

所以，又是一遍O(n)的计算就可以推出最终的答案

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 200100
#define ll long long
inline ll read()
{
      register ll x=0,t=1;
      register char ch=getchar();
      while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
      if(ch=='-'){t=-1;ch=getchar();}
      while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}
      return x*t;
}

ll dis[MAX],C[MAX],Q[MAX],f[MAX],Sum,Ans=1000000000000000000;

struct Line
{
      ll v,next,w;
}e[MAX];

ll h[MAX],cnt=1,N;

inline void Add(ll u,ll v,ll w)
{
      e[cnt]=(Line){v,h[u],w};
      h[u]=cnt++;
}
//使用两遍DFS
//第一遍以任意点为根节点计算一遍
//dis[i]表示以i为根的子树到根的距离之和 
ll DFS(ll u,ll ff)
{
      ll tot=0;
      for(ll i=h[u];i;i=e[i].next)
      {
               ll v=e[i].v;
               if(v!=ff)
               {
                      ll s=DFS(v,u);//子树上牛的数量 
                      dis[u]+=dis[v]+e[i].w*s;//统计 
                   tot+=s;//牛的个数
               }
      }
      return Q[u]=tot+C[u];
}
//第二遍计算偏移后的值
//先可以假设走到当前节点的父节点
//再让当前自己点所有牛退回来，父节点的所有牛走过去即可 
void DFS2(ll u,ll ff)
{
       for(ll i=h[u];i;i=e[i].next)
       {
                  ll v=e[i].v;
                  if(v!=ff)
                  {
                           ll ss=e[i].w;
                           f[v]=f[u]-Q[v]*ss+(Sum-Q[v])*ss;
                           DFS2(v,u);
                  }
       }
}

int main()
{
      N=read();
      for(ll i=1;i<=N;++i)
        C[i]=read();
      for(ll i=1;i<=N;++i)
        Sum+=C[i];//统计牛的总数 
      for(ll i=1;i<N;++i)
      {
                 ll u=read(),v=read(),w=read();
                 Add(u,v,w);
                 Add(v,u,w);
      }

      DFS(1,1);//求出以1为聚集处的结果 

      DFS2(1,1);//求出其他的偏移值

      for(ll i=1;i<=N;++i)
            Ans=min(Ans,f[i]);

        cout<<Ans+dis[1]<<endl;

        return 0;
}