首先这道题是在树上进行的，然后求最小的不方便程度，比较符合dp的性质，那么我们就可以搞一搞树形dp。

设计状态：f[i]表示以i作为聚集地的最小不方便程度。那么我们还需要各点间的距离，但是由于本题数据加强到1e5，开二维数组显然是不现实的，我们可以换一种思路，求d[i]表示其他所有奶牛到 i点的距离和，这样就成功转化过来惹==。

d[u]+=d[v]+size[v]*edge[i].val

然后再预处理size[i]数组表示以i为根的子树上奶牛的数量。这些都是一遍dfs就能搞定的，然后本题其实开始是无根树，这里默认1为根，看做有根树惹==。

 

转移：我们易知本题的转移是从当前状态转移到未来状态的。冷静分析可得

f[v]=f[u]-size[v]*edge[i].val+(cnt-size[v])*edge[i].val

然后本题中出现几次的转化思想，如上述方程中的cnt在中也有体现。

Code

1 #include
      
        2 #include
       
         3  4 using namespace std; 5 typedef long long ll; 6  7 int n,tot; 8 ll ans=1e40,cnt,size[100090],d[100090],f[100090]; 9 ll val[100090];10 ll head[100090];11 struct node{12     ll to,next,val;13 }edge[100090*2];14 15 ll lmin(ll a,ll b)16 {17     if(a
       
      

细节：本题开long long是毋庸置疑的，我开始把ans初值赋成了0x3f3f3f3f,在一般情况下本来够用，但是因为本题数据较大，所以在这种环境下就显得偏小了，可开到1e40.