HDU5886 Tower Defence 【两遍树形dp】【最长链预处理】

题意：N个点的一棵带权树。切掉某条边的价值为切后两树直径中的最大值。求各个边切掉后的价值和（共N-1项）。

解法一：

强行两遍dp，思路繁琐，维护东西较多：

dis表示以i为根的子树的直径，dis2表示切掉以i为根的子树后的直径。

第一遍dp，记录

  down[][0]:从i结点向下的最大距离

  down[][1]:与down[][0]无交集的向下次大距离

  dis:以i为根的子树的直径

第二遍dp，记录

  up:从i结点向上的最远距离, 可以是w+父节点的up，也可以是w+父节点的down（判断一下down是否与w有重合）

  dis2:切掉以i为根的子树后的直径

#include 
using namespace std;
#define X first
#define Y second
#define pii pair
#define mp make_pair
typedef long long ll;
const int N = 1e5+5;
void gmax(int& a, int b){ if(a < b) a = b;}
int n;
ll ans;
int down[N][2], up[N], dis[N], dis2[N];

int head[N], nex[N*2], tot;
pii edge[N*2];
void init(){
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(down, 0, sizeof(down));
    memset(up, 0, sizeof(up));
    memset(dis, 0, sizeof(dis));
    memset(dis2, 0, sizeof(dis2));
}
void add(int u, int v, int w){
    edge[tot] = mp(v, w);
    nex[tot] = head[u];
    head[u] = tot++;
}
//down[][0]:从i结点向下的最大距离
//down[][1]:与down[][0]无交集的向下次大距离
//dis:以i为根的子树的直径
void dfs(int fa, int x){
//    printf("dfs x %d, fa %d
", x, fa);
//down[x][0] = down[x][1] = dis[x] = dis2[x] = up[x] = 0;
    for(int i = head[x]; ~i; i = nex[i]){
        int y = edge[i].X, w = edge[i].Y;
        if(y == fa) continue ;
        dfs(x, y);
        if(down[y][0]+w > down[x][0])
            down[x][1] = down[x][0], down[x][0] = down[y][0]+w;
        else if(down[y][0]+w > down[x][1])
            down[x][1] = down[y][0]+w;
        gmax(dis[x], dis[y]);
    }
    gmax(dis[x], down[x][0]+down[x][1]);
}
//up:从i结点向上的最远距离
//dis2:切掉以i为根的子树后的直径
multiset<int>::iterator it;
void dfs2(int fa, int x){
    if(fa != -1) ans += max(dis[x], dis2[x]);
//    printf("fa %d, x %d
", fa, x);
    multiset<int> se, se2;//兄弟树的直径, x往各个兄弟树的最长路
    for(int i = head[x]; ~i; i = nex[i]){
        int y = edge[i].X, w = edge[i].Y;
        if(y == fa) continue ;
        se.insert( dis[y] );
        se2.insert( down[y][0]+w );
    }
    for(int i = head[x]; ~i; i = nex[i]){
        int y = edge[i].X, w = edge[i].Y;
        if(y == fa) continue ;
        up[y] = up[x]+w;
        if(down[y][0]+w == down[x][0])
            gmax(up[y], down[x][1]+w);
        else gmax(up[y], down[x][0]+w);
        it = se.find( dis[y] ), se.erase(it);
        it = se2.find( down[y][0]+w ), se2.erase(it);
        dis2[y] = dis2[x];
        if(!se.empty())
            gmax(dis2[y], *se.rbegin());
        if(se2.empty()) gmax(dis2[y], up[x]);
        else gmax(dis2[y], up[x]+*se2.rbegin());
        if(se2.size() >= 2){
            int tmp = 0;
            it = se2.end();
            tmp += *--it;
            tmp += *--it;
            gmax(dis2[y], tmp);
        }
        dfs2(x, y);
        se.insert( dis[y] );
        se2.insert( down[y][0]+w );
    }
}
void debug(int n){
    for(int i = 1; i <= n; i++)
        printf("%d: down0 %d, down1 %d, dis %d, dis2 %d, up %d
", i, down[i][0], down[i][1], dis[i], dis2[i], up[i]);
}
int main(){
    int t, u, v, w; scanf("%d", &t);
    while(t--) {
        init();
        scanf("%d", &n);
        for(int i = 1; i < n; i++){
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w), add(v, u, w);
        }
        ans = 0;
        dfs(-1, 1);
        dfs2(-1, 1);
        printf("%lld
", ans);
    }
    return 0;
}

 

解法二：

先求出原树的直径。

从直径两端分别来一次dp

切的边不在直径上，价值为直径；

切的边在直径上，由直径两端的dp得解。