方法一:动态规划加数据结构算法(写的时候我没想到这种做法,是来自题解区的,我给学会了,也欢迎到洛谷题解区去学习)

#include <bits/stdc++.h>
using namespace std;
#define rne(a) for(register int i = h[a]; i != -1 ; i=ne[i])
const int N = 1e5 + 10;
int n,a,b,c,w[N],idx=0,h[N],e[N],siz[N],f[N],ne[N],ans=0x3f3f3f3f;
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int x,int a,int b)//
{
    rne(x) {
        int j = e[i];
        if(j==a) continue;
        f[1]+=(b+1)*w[j];
        dfs(j,x,b+1);
        siz[x]+=siz[j];
    }
}
void dp(int x,int a)
{
    rne(x) {
        int j = e[i];
        if(a==j) continue;
        f[j]=f[x]+siz[1]-2*siz[j];
        ans = min(ans,f[j]);
        dp(j,x);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin >> n;
    for(int i = 1 ; i <= n ; i++) {
        cin >> w[i] >> b >> c;
        siz[i]=w[i];
        if(c) add(i,c),add(c,i);
        if(b) add(i,b),add(b,i);
    } 
    dfs(1,0,0);ans = f[1];
    dp(1,0);
    cout << ans << endl;
    return 0;
}

方法二:裸数据结构(本蒟的写法[自豪😂])

#include <bits/stdc++.h>
using namespace std;
struct node{
    int val,ls,rs,fls,frs,id;
}tree[100010];
queue<node> q;
int main()
{
    int n;cin >> n;
    for(int i = 1 ; i <= n; i ++) {
        cin >> tree[i].val >> tree[i].ls >> tree[i].rs;tree[i].id=i;
        if(tree[i].ls) tree[tree[i].ls].frs=i;
        if(tree[i].rs) tree[tree[i].rs].fls=i;
    }
    for(int i =  1;  i <= n ; i++) q.push({tree[i].val,tree[i].ls,tree[i].rs,tree[i].fls,tree[i].frs,i});
    int ans = 0x3f3f3f3f;
    while(q.size()) {
        int st[100010]={0},dis[100010]={0}; 
        auto tt = q.front();q.pop();
        st[tt.id]++;
        int sum=0;
        queue<node> cq;
        //cout << tt.val << " " << tt.ls << " " << tt.rs << " " << tt.fls << " " << tt.frs << endl; 
        cq.push(tt);
        while(cq.size()) {
            auto t=cq.front();cq.pop();
            //cout << t.val << " " << t.ls << " " << t.rs << " " << t.fls << " " << t.frs << endl; 
            if(t.ls&&(!st[t.ls])) {
                int j = t.ls;
                sum+=tree[j].val*(dis[t.id]+1);dis[j]=dis[t.id]+1; 
                st[tree[j].id]++;
                cq.push({tree[j].val,tree[j].ls,tree[j].rs,tree[j].fls,tree[j].frs,tree[j].id});
                //cout << sum << endl; 
            }if(t.rs&&!st[t.rs]) { 
                int j = t.rs;
                sum+=tree[j].val*(dis[t.id]+1);dis[j]=dis[t.id]+1;
                st[tree[j].id]++;
                cq.push({tree[j].val,tree[j].ls,tree[j].rs,tree[j].fls,tree[j].frs,tree[j].id});
                //cout << sum << endl; 
            }if(t.frs&&!st[t.frs]) {
                int j = t.frs;
                sum+=tree[j].val*(dis[t.id]+1);dis[j]=dis[t.id]+1;
                st[tree[j].id]++;
                cq.push({tree[j].val,tree[j].ls,tree[j].rs,tree[j].fls,tree[j].frs,tree[j].id});
                //cout << sum << endl; 
            }if(t.fls&&!st[t.fls]) {
                int j = t.fls;
                sum+=tree[j].val*(dis[t.id]+1);dis[j]=dis[t.id]+1;
                st[tree[j].id]++;
                cq.push({tree[j].val,tree[j].ls,tree[j].rs,tree[j].fls,tree[j].frs,tree[j].id});
                //cout << sum << endl; 
            }
        }
        //cout << sum << endl;
        //cout << "----------------------" << endl;
        ans=min(ans,sum);
    }
    cout << ans << endl;
    return 0;
}

方法三:BFS(主打一个广!!![自豪])

#include <bits/stdc++.h>
using namespace std;
#define maxn  100010
#define rep(a,b,c) for(register int i = a;i<=b;i+=c)
#define rne(a) for(register int j = h[a];j!=-1;j=ne[j])
int n,a,b,e[maxn],ne[maxn],h[maxn],idx=0,w[maxn],ans=0x3f3f3f3f;
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void bfs()
{
    rep(1,n,1) {
        queue<int> q;
        int dis[maxn]={0},sum=0,st[maxn]={0}; 
        q.push(i);
        st[i]=1;
        while(q.size()) {
            int t = q.front();q.pop();
            rne(t) {
                int jj = e[j];
                if(st[jj]||jj==0) continue;
                st[jj]=1;
                dis[jj]=dis[t]+1;
                sum+=dis[jj]*w[jj];
                q.push(jj); 
            }
        }
        ans = min(sum,ans);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin >> n;
    rep(1,n,1) {
        cin >> w[i] >> a >> b;
        add(i,a);add(i,b);
        add(a,i);add(b,i);
    } 
    bfs();
    cout << ans << endl;
    return 0;
}

方法四:Floyd算法

众所周知,floyd算法是一个动态规划算法

#include <bits/stdc++.h>
using namespace std;
const int N = 1000,INF=0x3f3f3f3f;
int d[N][N],a,b,c,w[N*N];
int main()
{
    int n;cin >> n;
    for(int i = 1 ; i <= n ; i++) 
        for(int j = 1 ; j <= n ; j++) 
            if(i==j) d[i][j]=0;
            else d[i][j]=INF;
    for(int i = 1; i<=n ; i++) {
        cin >> w[i] >> b >> c;
        if(b) d[i][b]=d[b][i]=1;
        if(c) d[i][c]=d[c][i]=1;
    }
    for(int k = 1 ; k <= n ; k++) {
        for(int i = 1 ; i<= n ;i++) {
            for(int j = 1 ; j <= n ; j++) {
                if(k!=i&&k!=j&&d[i][k]+d[k][j]<d[i][j]) d[i][j]=d[i][k]+d[k][j];
            }
        }
    }
    int ans = 0x3f3f3f3f,ts=0;
    for(int i = 1 ; i <= n ; i++) {
        ts=0;
        for(int j = 1 ; j <= n ; j++) {
            ts+=d[i][j]*w[j];
        }
        ans = min(ts,ans);
    }
    cout << ans << endl;
    return 0;
}