526互联

洛谷 P2986 [USACO10MAR] Great Cow Gathering G（树形DP/换根DP）

发布时间 2023-03-29 17:03:59作者: 高尔赛凡尔娟

https://www.luogu.com.cn/problem/P2986

输入 #1 
5 
1 
1 
0 
0 
2 
1 3 1 
2 3 2 
3 4 3 
4 5 3 
输出 #1 
15

推荐这位佬的思路以及题解
https://zhuanlan.zhihu.com/p/571948153

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=1e5+10,M=4023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL n,ans[N];
map<LL,LL> mp;
vector<PII> v[N];
LL sum=0;
void dfs1(int idx,int fa)//当前节点，父节点
{
    for(int i=0;i<v[idx].size();i++)
    {
        PII t=v[idx][i];
        int to=t.first,distance=t.second;//下一个节点，两地距离
        if(to==fa) continue;//与父节点重复，跳出
        dfs1(to,idx);//继续深搜
        mp[idx]+=mp[to];//父节点的奶牛数量直接加上当前点往下的（距离更加遥远的奶牛）
        ans[idx]+=ans[to]+mp[to]*distance;//总路程就等于我下一个要去的地方加上下一个地方的所有奶牛要跑的路程
    }
}
void dfs2(int idx,int fa)
{
    for(int i=0;i<v[idx].size();i++)
    {
        PII t=v[idx][i];
        int to=t.first,distance=t.second;
        if(to==fa) continue;
        ans[to]=ans[idx]-mp[to]*distance+(sum-mp[to])*distance;//换根时注意还原
        dfs2(to,idx);
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>mp[i];
            sum+=mp[i];//sum记录全部奶牛数量
        }
        for(int i=1;i<=n-1;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            v[a].push_back({b,c});//添加双向边
            v[b].push_back({a,c});
        }
        dfs1(1,-1);//从1开始,父节点为-1
        dfs2(1,-1);//从1开始,父节点为-1
        LL minn=MAXN;
        for(int i=1;i<=n;i++)
        {
            minn=min(minn,ans[i]);
        }
        cout<<minn<<endl;
    }
    return 0;
}