您的位置: 首页  >  IT文章  >  树形dp小结

树形dp小结

分类: IT文章 • 2025-01-21 11:23:37

地址：https://vjudge.net/contest/168217

最近做了大量的dp，同时完成了一套树形dp，刷tc的时候也做了好几道树形dp。 <del>感觉会做dp了</del>

先训练，有空再补上

HDU 1520 Anniversary party (入门中的入门)

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

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 6005;

int n;
int e[maxn];
int dp[maxn][2];
vector<int> v[maxn];

void dfs(int x,int f)
{
    dp[x][0] = e[x];
    dp[x][1] = 0;
    for(int i = 0; i < v[x].size(); i++)
    {
        int c = v[x][i];
        if(c == f) continue;
        dfs(c,x);
        dp[x][0] += dp[c][1];
        dp[x][1] += max(dp[c][0],dp[c][1]);
    }
}

int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    while(scanf("%d",&n) == 1)
    {
        for(int i = 1; i <= n; i++) {scanf("%d",e + i);v[i].clear();}
        int a,b;
        while(scanf("%d%d",&a,&b) && a)
        {
            v[a].push_back(b);
            v[b].push_back(a);
        }
        dfs(1,0);
        printf("%d
",max(dp[1][0],dp[1][1]));
    }
    return 0;
}
HDU 1520

HDU 2196 Computer 

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

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 100005;

int n,m;
int dp[maxn][2],id[maxn][2];
vector<int> v[maxn];
struct Edge
{
    int to,len;
    Edge(int a = 0,int b = 0):to(a),len(b){}
}edges[maxn<<1];

void upd(int& a,int& b,int c,int d,int e)
{
    a = c + d;
    b = e;
}

void dfs1(int x,int f)
{
    dp[x][0] = dp[x][1] = 0;
    id[x][0] = id[x][1] = 0;
    for(int i = 0; i < v[x].size(); i++)
    {
        int c = v[x][i];
        int to = edges[c].to;
        if(to == f)
            continue;
        dfs1(to,x);
        if(dp[x][0] < dp[to][0] + edges[c].len)
        {
            dp[x][1] = dp[x][0];
            id[x][1] = id[x][0];
            upd(dp[x][0],id[x][0],dp[to][0],edges[c].len,to);
        }
        else if(dp[x][1] < dp[to][0] + edges[c].len)
            upd(dp[x][1],id[x][1],dp[to][0],edges[c].len,to);
    }
}

void dfs2(int x,int f,int l)
{
    if(id[f][0] != x)
    {
        if(dp[x][0] < dp[f][0] + l)
        {
            dp[x][1] = dp[x][0];
            id[x][1] = id[x][0];
            upd(dp[x][0],id[x][0],dp[f][0],l,f);
        }
        else if(dp[x][1] < dp[f][0] + l)
            upd(dp[x][1],id[x][1],dp[f][0],l,f);
    }
    else 
    {
        if(dp[x][0] < dp[f][1] + l)
        {
            dp[x][1] = dp[x][0];
            id[x][1] = id[x][0];
            upd(dp[x][0],id[x][0],dp[f][1],l,f);
        }
        else if(dp[x][1] < dp[f][1] + l)
            upd(dp[x][1],id[x][1],dp[f][1],l,f);
    }
    for(int i = 0; i < v[x].size(); i++)
        if(edges[v[x][i]].to != f)
            dfs2(edges[v[x][i]].to,x,edges[v[x][i]].len);
}

int main()
{
    //freopen("b.in","r",stdin);
    //freopen("b.out","w",stdout);
    while(scanf("%d",&n) == 1)
    {
        m = 0;
        for(int i = 1; i <= n; i++) v[i].clear();
        for(int i = 2; i <= n; i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            edges[m] = Edge(a,b);
            v[i].push_back(m++);
            edges[m] = Edge(i,b);
            v[a].push_back(m++);
        }
        memset(dp,0,sizeof dp);
        dfs1(1,0);
        dp[0][0] = dp[0][1] = id[0][0] = id[0][1] = 0;
        dfs2(1,0,0);
        for(int i = 1; i <= n; i++)
            printf("%d
",dp[i][0]);
    }
    return 0;
}
HDU 2196

CodeForces 219D Choosing Capital for Treeland

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

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 200005;

int n;
int d[maxn],cal[maxn];
struct Edge
{
    int to,k;
    Edge(int a = 0,int b = 0):to(a),k(b){}
}edges[maxn<<1];
vector<int> v[maxn];

void dfs1(int x,int f)
{
    d[x] = cal[x] = 0;
    for(int i = 0; i < v[x].size(); i++)
    {
        int e = v[x][i];
        int to = edges[e].to;
        if(to == f) continue;
        dfs1(to,x);
        d[x] += d[to] + edges[e].k ;
        cal[x] += cal[to] + 1;    
    }
}

int ans;
void dfs2(int x,int f,int k)
{
    if(f) d[x] += d[f] - d[x] - k + (k ^ 1);
    if(d[x] < ans) ans = d[x];
    for(int i = 0; i < v[x].size(); i++)
    {
        int e = v[x][i];
        int to = edges[e].to;
        if(to != f) dfs2(to,x,edges[e].k);
    }
}

int main()
{
    //freopen("c.in","r",stdin);
    //freopen("c.out","w",stdout);
    scanf("%d",&n);
    int m = 0;
    for(int i = 0; i < n - 1; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        edges[m] = Edge(b,0);
        v[a].push_back(m++);
        edges[m] = Edge(a,1);
        v[b].push_back(m++);
    }
    dfs1(1,0);
    //for(int i = 1; i <= n; i++) cout<<d[i]<<endl;
    //cout<<endl;
    ans = 1 << 30;
    dfs2(1,0,0);
    //for(int i = 1; i <= n; i++) cout<<d[i]<<endl;
    //cout<<endl;
    printf("%d
",ans);
    for(int i = 1; i <= n; i++) 
        if(d[i] == ans) printf("%d ",i);
    printf("
");
    return 0;
}
CodeForces - 219D

HDU 3586 Information Disturbing

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

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1005;

int n,m;
int dp[maxn],cal[maxn];
int to[maxn<<1],len[maxn<<1];
vector<int> v[maxn];

int cnt;
void addEdge(int a,int b,int l)
{
    to[++cnt] = b;
    len[cnt] = l;
    v[a].push_back(cnt);
}

void upd(int& a,int b)
{
    if(a == -1) a = b;
    else a = max(a,b);
}

void dfs(int x,int fa)
{
    if(x != 1 && v[x].size() == 1) 
    {
        dp[x] = -1;
        return;
    }
    dp[x] = -1;
    cal[x] = 0;
    for(int i = 0; i < v[x].size(); i++)
    {
        int c = v[x][i];
        if(to[c] == fa) continue;
        dfs(to[c],x);
        //if(x == 1) cout<<to[c]<<" "<<dp[to[c]]<<endl;
        if(dp[to[c]] == -1)
        {
            upd(dp[x],len[c]);
            cal[x] += len[c];
        }
        else 
        {
            upd(dp[x],min(dp[to[c]],len[c]));
            cal[x] += min(cal[to[c]],len[c]);
        }
    }
}

int main()
{
    //freopen("d.in","r",stdin);
    //freopen("d.out","w",stdout);
       while(scanf("%d%d",&n,&m) == 2)
    {
        if(!n && !m) break;
        for(int i = 1; i <= n; i++) v[i].clear();
        cnt = 0;
        for(int i = 0; i < n - 1; i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            addEdge(a,b,c);
            addEdge(b,a,c);
        }
        dfs(1,0);
        printf("%d
",cal[1] > m ? -1 : dp[1]);
    }
       return 0;
}
HDU 3586

POJ 3162 Walking Race

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1000005;

int n,m;
int head[maxn],nxt[maxn<<1],to[maxn<<1],len[maxn<<1];
ll dp[maxn][2];
int id[maxn];
ll dist[maxn];

int cnt;
void addEdge(int a,int b,int c)
{
    to[++cnt] = b;
    len[cnt] = c;
    nxt[cnt] = head[a];
    head[a] = cnt;
}

void dfs(int x,int fa)
{
    dp[x][0] = dp[x][1] = 0;
    id[x] = 0;
    for(int i = head[x]; i; i = nxt[i])
    {
        if(to[i] == fa) continue;
        dfs(to[i],x);
        if(dp[x][0] < dp[to[i]][0] + len[i])
        {
            dp[x][1] = dp[x][0];
            dp[x][0] = dp[to[i]][0] + len[i];
            id[x] = i;
        }
        else if(dp[x][1] < dp[to[i]][0] + len[i])
            dp[x][1] = dp[to[i]][0] + len[i];
    }
}

void getdis(int x,int fa,ll dis)
{
    dist[x] = 1LL * max(dis,dp[x][0]);
    for(int i = head[x]; i; i = nxt[i])
    {
        if(to[i] == fa) continue;
        ll tmp = 0;
        if(id[x] == i)
            tmp = max(dis,dp[x][1]) + len[i];
        else 
            tmp = max(dis,dp[x][0]) + len[i];
        getdis(to[i],x,tmp);
    }
}

ll mx[maxn<<2],mi[maxn<<2];
void build(int l,int r,int o)
{
    if(l == r)
    {
        mx[o] = mi[o] = dist[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l,mid,o << 1);
    build(mid + 1,r,o << 1 | 1);
    mx[o] = max(mx[o << 1],mx[o << 1 | 1]);
    mi[o] = min(mi[o << 1],mi[o << 1 | 1]);
}

int ql,qr;
ll qmx,qmi;
void que(int l,int r,int o)
{
    if(ql <= l && qr >= r)
    {
        qmx = max(qmx,mx[o]);
        qmi = min(qmi,mi[o]);
        return;
    }
    int mid = (l + r) >> 1;
    if(mid >= ql) que(l,mid,o << 1);
    if(mid < qr) que(mid + 1,r,o << 1 | 1);
}

int main()
{
    //freopen("e.in","r",stdin);
    //freopen("e.out","w",stdout);
    scanf("%d%d",&n,&m);
    cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        addEdge(i,a,b);
        addEdge(a,i,b);
    }
    dfs(1,0);
    getdis(1,0,0);
    //for(int i = 1; i <= n; i++) cout<<dist[i]<<" ";
    //cout<<endl;
    build(1,n,1);
    int ans = 0;
    int l = 1,r = 1;
    while(r <= n)
    {
        ql = l; qr = r;
        qmx = 0; qmi = 1e18;
        que(1,n,1);
        if(qmx - qmi <= m)
        {
            ans = max(ans,r - l + 1);
            r++;
        }
        while(qmx - qmi > m)
        {
            l++;
            ql = l; ql = r;
            qmi = 1e18; qmx = 0LL;
            que(1,n,1);
        }
    }
    printf("%d
",ans);
    return 0;
}
POJ 3162

HDU 5834 Magic boy Bi Luo with his excited tree

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

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 100005;

int T;
int n;
int v[maxn];
int to[maxn<<1],w[maxn<<1],head[maxn],nxt[maxn<<1];
int not_back[maxn][2],id[maxn],back[maxn],ans[maxn];

int cnt;
void addEdge(int a,int b,int c)
{
    to[++cnt] = b;
    w[cnt] = c;
    nxt[cnt] = head[a];
    head[a] = cnt;
}

void dfs(int x,int fa)
{
    not_back[x][0] = not_back[x][1] = v[x];
    id[x] = 0;
    back[x] = v[x];
    for(int i = head[x]; i; i = nxt[i])
    {
        if(to[i] == fa) continue;
        dfs(to[i],x);
        back[x] += max(back[to[i]] - 2 * w[i],0);
    }
    for(int i = head[x]; i; i = nxt[i])
    {
        if(to[i] == fa) continue;
        int now = back[x] - max(0,back[to[i]] - 2 * w[i]) + max(0,not_back[to[i]][0] - w[i]);
        if(now > not_back[x][0])
        {
            not_back[x][1] = not_back[x][0];
            not_back[x][0] = now;
            id[x] = i;
        }
        else if(now > not_back[x][1])
            not_back[x][1] = now;
    }
}

void solve(int x,int fa,int b,int g)
{
    //cout<<endl;
    //cout<<x<<" "<<b<<" "<<g<<endl;
    ans[x] = max(not_back[x][0] + b,back[x] + g);
    for(int i = head[x]; i; i = nxt[i])
    {
        if(to[i] == fa) continue;
        int tb,tg;
        if(id[x] == i) tg = max(0,not_back[x][1] - max(0,back[to[i]] - 2 * w[i]));
        else tg = max(0,not_back[x][0] - max(0,back[to[i]] - 2 * w[i]));
        tb = max(0,back[x] - max(0,back[to[i]] - 2 * w[i]));
        tg = max(0,max(g + tb - w[i],tg + b - w[i]));
        tb = max(0,b + tb - 2 * w[i]);
        solve(to[i],x,tb,tg);
    }
}

int main()
{
    //freopen("f.in","r",stdin);
    //freopen("f.out","w",stdout);
    scanf("%d",&T);
    for(int kase = 1; kase <= T; kase++)
    {
        memset(head,0,sizeof head);
        scanf("%d",&n);
        for(int i = 1; i <= n; i++) scanf("%d",v + i);
        cnt = 0;
        for(int i = 0; i < n - 1; i++) 
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            addEdge(a,b,c);
            addEdge(b,a,c);
        }
        //cout<<endl;
        dfs(1,0);
        //cout<<endl;
        solve(1,0,0,0);
        printf("Case #%d:
",kase);
        for(int i = 1; i <= n; i++)
            printf("%d
",ans[i]);
    }
    return 0;
}
HDU 5834

POJ 2152 Fire

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1005;
const int INF = 1 << 30;

int T,n;
int w[maxn],d[maxn];
int dis[maxn][maxn],best[maxn],dp[maxn][maxn];//第i个城市以第j个城市为防火负责点
int head[maxn],to[maxn<<1],nxt[maxn<<1],len[maxn<<1];

int cnt;
void addEdge(int a,int b,int c)
{
    to[++cnt] = b;
    len[cnt] = c;
    nxt[cnt] = head[a];
    head[a] = cnt;
}

void init()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",w + i);
    for(int i = 1; i <= n; i++) scanf("%d",d + i);
    cnt = 0;
    memset(head,0,sizeof head);
    for(int i = 1; i <= n; i++) 
    {
        best[i] = INF;
        for(int j = 1; j <= n; j++) 
            dp[i][j] = INF;
    }
    for(int i = 1; i < n; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        addEdge(a,b,c);
        addEdge(b,a,c);
    }
}

void dfs(int x,int fa,int dist,int root)
{
    dis[root][x] = dist;
    for(int i = head[x]; i; i = nxt[i])
    {
        if(to[i] == fa) continue;
        dfs(to[i],x,dist + len[i],root);
    }
}

void solve(int u,int fa)
{
    for(int i = 1; i <= n; i++)
        if(dis[u][i] <= d[u])
            dp[u][i] = w[i];
    for(int i = head[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(v == fa) continue;
        solve(v,u);
        for(int j = 1; j <= n; j++)
            if(dis[u][j] <= d[u])
                      dp[u][j] += min(dp[v][j] - w[j],best[v]);       
    }
    for(int i = 1; i <= n; i++) 
        best[u] = min(best[u],dp[u][i]);
}

int main()
{
    //freopen("g.in","r",stdin);
    //freopen("g.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        init();
        for(int i = 1; i <= n; i++) 
            dfs(i,0,0,i);
        solve(1,0);
        printf("%d
",best[1]);
    }
    return 0;
}
POJ 2152

POJ 1741 Tree

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 10005;

int n,k,m;
int vis[maxn],f[maxn],son[maxn];
int dep[maxn],d[maxn];
int to[maxn<<1],len[maxn<<1],next[maxn<<1],head[maxn<<1];

void addEdge(int u,int v,int l)
{
    to[++m] = v;
    len[m] = l;
    next[m] = head[u];
    head[u] = m;
}

int root,sn;
void getroot(int x,int fa)
{
    son[x] = 1; f[x] = 0;
    for(int i = head[x]; i; i = next[i])
    {
        if(to[i] == fa || vis[to[i]]) continue;
        getroot(to[i],x);
        son[x] += son[to[i]];
        f[x] = max(f[x],son[to[i]]);
    }
    f[x] = max(f[x],sn - son[x]);
    if(f[root] > f[x]) root = x;
}

int cnt;
void getdeep(int x,int fa)
{
    d[cnt++] = dep[x];
    for(int i = head[x]; i; i = next[i])
    {
        if(to[i] == fa || vis[to[i]]) continue;
        dep[to[i]] = dep[x] + len[i];
        getdeep(to[i],x);
    }
}

int cal(int x)
{
    cnt = 0;
    getdeep(x,0);
    sort(d,d + cnt);
    int ret = 0;
    int i = 0, j = cnt - 1;
    while(i < j)
    {
        while(d[i] + d[j] > k && i < j) j--;
        ret += j - i;
        i++;
    }
    return ret;
}

int solve(int x)
{
    dep[x] = 0;
    vis[x] = 1;
    int ans = cal(x);
    for(int i = head[x]; i; i = next[i])
    {
        if(vis[to[i]]) continue;
           dep[to[i]] = len[i];
        ans -= cal(to[i]);
        sn = son[to[i]];
        root = 0; getroot(to[i],0);
        ans += solve(root);    
    }
    return ans;
}


int main()
{
    //freopen("h.in","r",stdin);
    //freopen("h.out","w",stdout);
    while(scanf("%d%d",&n,&k) == 2)
    {
        if(!n && !k) break;
        m = 0;
        memset(next,0,sizeof next);
        memset(head,0,sizeof head);
        for(int i = 1; i < n; i++)
        {
            int u,v,l;
            scanf("%d%d%d",&u,&v,&l);
            addEdge(u,v,l);
            addEdge(v,u,l);
        }
        memset(vis,0,sizeof vis);
        f[0] = 1e9; sn = n;
        root = 0; getroot(1,0);
        printf("%d
",solve(root));
    }
    return 0;
}
POJ 1741

TC SRM 693 DIV2 1000

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

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 105;
const int INF = 1 << 29;

int n,tot;
int vis[maxn],nod[maxn];
int g[maxn][maxn];
int dp[maxn][3];

void dfs(int x,int fa)
{
    int l1,l2;
    l1 = l2 = -1e9;
    dp[x][0] = dp[x][1] = dp[x][2] = 0;
    for(int i = 0; i < n; i++)
    {
        if(g[x][i] == 0 || i == fa) continue;
        dfs(i,x);
        int t1 = max(dp[i][0],dp[i][1]);
        int t2 = max(t1,dp[i][2]);
        int t3 = t1 - t2 + nod[i] + g[x][i];
        dp[x][0] += t2;
        if(t3 >= l1) { l2 = l1; l1 = t3; }
        else if(t3 > l2) l2 = t3;    
    }
    dp[x][1] = l1 + nod[x] + dp[x][0];
    dp[x][2] = l1 + l2 + 2 * nod[x] + dp[x][0];

}

class TreeAndCycle
{
    public:
        int minimize(vector<int> costV,vector<int> pre,vector<int> costE)
        {
            n = costV.size();
            memset(g,0,sizeof g);
            tot = 0;
            for(int i = 0; i < n; i++) 
            {
                nod[i] = costV[i];
                tot += 2 * costV[i];
            }
            for(int i = 0; i < n - 1; i++)
            {
                tot += costE[i];
                g[i+1][pre[i]] = g[pre[i]][i+1] = costE[i];
            }
            dfs(0,0);
            return tot - max(dp[0][0],max(dp[0][1],dp[0][2]));
        }
};
TC SRM 639 1000

相关推荐