树形 DP 复习 note

请‎输‎入‎文‎本‎. ‎🐛‎

2026-08-31 22:47:49

发布于：上海

51阅读

0回复

0点赞

这玩意儿已经在 114514 年前发过 note ，但是现在早已忘记了，写得也比较省略，并且 GGSP 编程题也考到了 ~~我就不信了还会再考树形 DP~~ ，所以全网最区的帖主发布了复习 note

树形 DP ，本质就是利用数组储存每个结点的状态值（子树的 xxx 信息），然后根据父子关系确定状态转移方程，不过这里要注意方向：
如果父→子，遍历直接遍历下去，大法师子结点
如果子→父，先大法师子结点，然后回溯时进行更新

P2052
这道题可以将每条道路看为父子关系，然后子结点一端的国家个数即为子树大小，再计算父结点一端的国家个数，就可以得到这条道路的费用了，转移方程 $dp[x]=1+Σ_{fa[y]=x}dp[y]$

namespace HQ{
    using ll=long long;
    void init(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);}
    inline ll read(){ll num=0,sign=1,ch;while((ch=getchar())==' ' or ch=='\n' or ch=='\t'){}if(ch=='-'){sign=-1;ch=getchar();}else if(ch=='+')ch=getchar();while(ch>='0' and ch<='9'){num=num*10+(ch-'0');ch=getchar();}return sign*num;}
    inline void write(ll n){if(n<0){putchar('-');n*=-1;}if(n>=10){write(n/10);}putchar(n%10+'0');}
    int n;
    struct node{
        ll v,w;
    };
    vector<node>ve[1145140];
    ll ans=0;
    int dp[1145140];
    bool vis[1145140];
    void dfs(ll x){
        vis[x]=1;
        dp[x]=1;
        for(int i=0;i<ve[x].size();++i){
            int y=ve[x][i].v;
            if(vis[y])continue;
            dfs(y);
            dp[x]+=dp[y];
            ans+=ve[x][i].w*abs(n-2*dp[y]);
        }
    }
    void Main(){
        init();
        cin>>n;
        for(int i=1;i<n;++i){
            int u,v,w;
            cin>>u>>v>>w;
            ve[u].push_back({v,w});
            ve[v].push_back({u,w});
        }dfs(1);
        cout<<ans;
        return;
    }
}