每日一题 4月13日 树学 和 Accumulation Degree 换根DP

思路：看到这个题要求所有点，肯定要换根，我们肯定要把f[1]求出来。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

vector<vector<int> > v(1000005);
int cut[1000005], f[1000005];
int ans=0, n;
void dfs(int u, int fa, int d){
    f[1]+=d;
    for(auto x: v[u]){
        if(x!=fa){
            dfs(x, u, d+1);
            cut[u]+=cut[x];
        }
    }
    cut[u]+=1;
}

void DFS(int u, int fa){
    for(auto x: v[u]){
        if(x!=fa){
            f[x]=f[u]-cut[x]+(n-cut[x]);
            DFS(x, u);
        }
    }
}

int main() {

    int x, y; scanf("%d", &n);
    for(int i=1; i<n; i++){
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 0, 0);
    DFS(1, 0);
    cout<<*min_element(f+1, f+1+n)<<endl;

    return 0;
}

思路：和上面的套路一样。就是转移的地方不一样

#include<bits/stdc++.h>
#define LL long long
using namespace std;

vector<vector<pair<int, int> > > v(200005);
int n, f[200005];

void dfs(int u, int fa){

    for(auto x: v[u]){
        int to=x.first, w=x.second;
        if(to!=fa){
            dfs(to, u);
            if(f[to]==0) f[u]+=w;
            else f[u]+=min(w, f[to]);
        }
    }
}

void DFS(int u, int fa){
    for(auto x: v[u]){
        int to=x.first, w=x.second;
        if(to!=fa){
            f[to]+=min(f[u]-min(f[to], w), w);
            DFS(to, u);
        }
    }
}

int main() {

    int t; scanf("%d", &t);
    while(t--){
        int x, y, z; scanf("%d", &n);
        for(int i=1; i<n; i++){
            scanf("%d%d%d", &x, &y, &z);
            v[x].push_back({y, z});
            v[y].push_back({x, z});
        }
        dfs(1, 0);
        DFS(1, 0);
        cout<<*max_element(f+1, f+1+n)<<endl;
        for(int i=1; i<=n; i++) v[i].clear(), f[i]=0;
    }

    return 0;
}