POJ.3585AccumulationDegree(树型DP)xiaodangao

题目链接：Accumulation Degree
题意：略
思路：利用一次dfs，可求出一点为源点的答案，我们将这一点设为x点，下一步dfs时，可以利用x点的答案推出他所有儿子节点的答案，因为x节点的答案已经知道，然后对于他每一个儿子节点（y），我们上一步dfs求出来他到除了x点以外的节点的答案（即他这棵关于x子树的答案），那么考虑该儿子节点作为源点的答案，答案为x节点的其他子树的贡献与边（x，y）的边权的取min再加上该节点子树的答案。不理解的同学可以画一棵树自己体会一下这个过程。

$Coding:$


/*************************************************************************
    > File Name: 3585.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
    > Created Time: 2021年03月29日 星期一 16时10分16秒
 ************************************************************************/

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define bep(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int N = 2e5+10;

//#define int long long 
int T;
int n,deg[N];
int f[N],ans[N];
vector<int>G[N],val[N];
bool st[N];
void dfs(int id){
    if(st[id])return ;    st[id] = true;
//    write(id);pc('\n');
    rep(i,0,(int)G[id].size()-1){
        int p = G[id][i];int v = val[id][i];
        if(st[p])continue;
        dfs(p);
        if(deg[p] != 1)
        f[id] += min(v,f[p]);
        else f[id] += v;
    }
}
int ANS = 0;
void getans(int id){
    if(st[id])return;
    st[id] = true;
    rep(i,0,(int)G[id].size()-1){
        int p = G[id][i],v = val[id][i];
        if(st[p])continue;
        int t = ans[id] - min(f[p],v);
        if(deg[id] == 1)t = v;
        int k = min(t,v);
        ans[p] = f[p] + k;
        if(deg[p] == 1)ans[p] = min(v,ans[p]);
        ANS = max(ANS,ans[p]);
    }
    rep(i,0,(int)G[id].size()-1){
        int p = G[id][i];
        getans(p);
    }
}
void init(){
    rep(i,1,n)G[i].clear(),val[i].clear();
    memset(st,0,sizeof st);
    memset(f,0,sizeof f);
    memset(ans,0,sizeof ans);
    memset(deg,0,sizeof deg);
}
void solve(){
    read(T);
    while(T--){
        read(n);
        ANS = 0;
        init();
        rep(i,1,n-1){
            int u,v,w;
            read(u);read(v);read(w);
            G[u].pb(v);
            G[v].pb(u);
            val[u].pb(w);
            val[v].pb(w);
            deg[u]++;deg[v]++;
        }
        dfs(1);
        memset(st,0,sizeof st);
        ans[1] = f[1];
        ANS = ans[1];
        getans(1);
        write(ANS);pc('\n');
    }
}
signed main(){
    solve();
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。