【算法与数据结构】——树形DP二次扫描与换根

迷南。 2022-09-10 01:15 191阅读 0赞

# 二次扫描与换根 #

在一棵无根树上需要以多个节点为根求解答案，可以运用二次扫描与换根法。具体操作是通过实现一次自底向上的深度优先搜索和一次自顶向下的深度优先搜索来计算“换根”后的解；  
（1）第1次扫描：任选一个结点为根出发，执行一次深度优先搜索，在递归回溯时自底向上进行状态转移，用子节点的状态更新父节点的状态  
（2）第2次扫描：从刚才选出的跟出发，再进行一次深度优先搜索，在每次递归前都自顶向下进行状态转移，用父节点的状态更新子节点的状态，计算出“换根”后的结果。

# 例题 Accumulation Degree #

题目地址[POJ 3585][]  
题目大意：a(x)表示书中节点x的累计度，定义如下：1.树的每个边都有一个正容量；  
2.树中度为1的节点叫作终端；  
3.每条边的流量不能超过其容量；  
4.a(x)是节点x可以流向其他终端节点的最大流量。  
树的累积度是树中节点的最大累积度。  
思路：  
二次扫描与换根。  
AC代码：

#include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <cstdio>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 1e6+5;
    int head[N],deg[N];
    struct Edge{ 
        int to;
        int val;
        int next;
    }E[N<<1];
    int d[N],dp[N];
    void init()
    { 
        for(int i = 1;i < N;i++)
        { 
            head[i] = -1;
            d[i] = 0;
            dp[i] = 0;
            deg[i] = 0;
        }
        memset(E,0,sizeof(E));
    }
    void DFS(int u,int fa)
    { 
        for(int i = head[u];i!=-1;i = E[i].next)
        { 
            int v = E[i].to;
            if(v == fa)
                continue;
            DFS(v,u);
            if(deg[v]==1)
            { 
                d[u]+=E[i].val;
            }
            else
            { 
                d[u]+=min(d[v],E[i].val);
            }
        }
    }
    void DFS2(int u,int fa)
    { 
        for(int i = head[u];i!=-1;i = E[i].next)
        { 
            int v = E[i].to;
            if(v == fa)
            { 
                continue;
            }
            if(deg[u]==1)
            { 
                dp[v]= d[v]+E[i].val;
            }
            else
            { 
                dp[v]=d[v]+min(dp[u]-min(d[v],E[i].val),E[i].val);
            }
            DFS2(v,u);
        }
    }
    void solve()
    { 
        int n;
        scanf("%d",&n);
        init();
        for(int i = 1;i <= (n-1)<<1;i+=2)
        { 
            int x, y, z;
            scanf("%d%d%d",&x, &y, &z);
            E[i].to = y;
            E[i].val = z;
            E[i].next = head[x];
            head[x] = i;
    
            E[i+1].to = x;
            E[i+1].val = z;
            E[i+1].next = head[y];
            head[y] = i+1;
    
            deg[x]++;
            deg[y]++;
        }
        DFS(1,0);
        dp[1] = d[1];
        DFS2(1,0);
    
        int ans = 0;
        for(int i = 1;i <= n;i++)
        { 
            ans = max(ans,dp[i]);
        }
        printf("%d\n",ans);
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // int t = 1;
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

# 树上最远距离 #

题目地址[HDU2196][]  
题目大意：给定一棵树，求每一个节点到其他节点的最长距离  
思路：关键就是求出一个节点向下的最长距离和向上的最长距离，用关于树上dp的思路  
AC代码：

#include <bits/stdc++.h>
    //#include <iostream>
    //#include <cstdio>
    //#include <cstring>
    //#include <algorithm>
    //#include <vector>
    //#include <map>
    //#include <stack>
    //#include <queue>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 10005;
    struct edge{ 
        int to;
        int v;
        int next;
    }E[N<<1];
    int head[N];
    int dp[N][3];//0表示u节点向下最远距离，1表示u节点向下次远距离，2表示u节点向上最远距离
    void init()
    { 
        for(int i = 1;i < N;i++)
        { 
            head[i] = -1;
        }
        memset(E,0,sizeof(E));
    }
    
    void DFS1(int u, int fa)
    { 
        dp[u][0] = 0;
        dp[u][1] = 0;
        for(int i = head[u];i!=-1;i = E[i].next)
        { 
            int v = E[i].to;
            if(v == fa)
            { 
                continue;
            }
            DFS1(v,u);
            if(dp[v][0] + E[i].v > dp[u][0])
            { 
                dp[u][1] = dp[u][0];
                dp[u][0] = dp[v][0] + E[i].v;
    
            }
            else if(dp[v][0] + E[i].v > dp[u][1])
            { 
                dp[u][1] = dp[v][0] + E[i].v;
            }
        }
    }
    
    void DFS2(int u, int fa)
    { 
        for(int i = head[u];i!=-1;i = E[i].next)
        { 
            int v = E[i].to;
            if(v == fa)
            { 
                continue;
            }
            dp[v][2] = 0;
            if(dp[u][0]-E[i].v == dp[v][0])
            { 
                dp[v][2] = max(dp[u][1],dp[u][2])+E[i].v;
            }
            else
            { 
                dp[v][2] = max(dp[u][0],dp[u][2])+E[i].v;
            }
            DFS2(v,u);
        }
    }
    
    void solve()
    { 
        int n;
    	while(scanf("%d",&n)!=EOF)
        { 
            init();
            for(int i = 1;i < (n-1)<<1;i+=2)
            { 
                int x, y;
                scanf("%d%d",&x,&y);
                E[i].to = x;
                E[i].v = y;
                E[i].next = head[(i+3)>>1];
                head[(i+3)>>1] = i;
    
                E[i+1].to = (i+3)>>1;
                E[i+1].v = y;
                E[i+1].next = head[x];
                head[x] = i+1;
            }
            DFS1(1,1);
            DFS2(1,1);
            for(int i = 1;i <= n;i++)
            { 
                printf("%d\n",max(dp[i][0],dp[i][2]));
            }
        }
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	int t = 1;
    // int t;
    // scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

[POJ 3585]: http://poj.org/problem?id=3585
[HDU2196]: https://acm.hdu.edu.cn/showproblem.php?pid=2196