HDU 4679 Terrorist’s destroy (樹形DP)

比賽中的時候由於前面算法考慮不全面，導致很快敲完但是接下來糾結了好久，照我原來那種方法寫，只能開好多個數組進行各種判斷，雖然還是A了，但是肯定是要學習下寫法簡單點的做法的。

題意：

給你一棵樹，每條邊都有權值，現在要求去掉一條邊後剩下的兩顆樹中較長的最長路乘上這條邊的權值最小，輸出那條邊的編號。如果有多解，輸出編號小的那個。

解題思路：

我自己的搓代碼和方法就不說了。賽後學到了新的方法，其實很簡單，只不過自己從沒這樣寫過。

先求出一條最長路，如果去掉的邊是不是這條最長路上的，那麼結果就是這條邊權值乘上最長路。

如果去掉的邊在這條最長路上，那就在最長路上分別雙向dfs一次，每次求出某節點以下子樹中的最長路。

附上代碼。

/* **********************************************
Author      : JayYe
Created Time: 2013-8-15 18:07:13
File Name   : zzz.cpp
*********************************************** */

#pragma comment(linker,"/STACK:100000000,100000000")

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn = 100000;

struct EDGE {
    int to, next, val, id;
}edge[maxn*2+10];

int head[maxn+10], E, dp[maxn+10][4], p[maxn+10], dep[maxn+10], ee[maxn+10];
bool vis[maxn+10];

void init(int n) {
    for(int i = 1;i <= n; i++)  head[i] = -1;
    E = 0;
}

void newedge(int u, int to, int val, int id) {
    edge[E].to = to;
    edge[E].val = val;
    edge[E].id = id;
    edge[E].next = head[u];
    head[u] = E++;
}

// 求出每個節點的深度， 深度最大的肯定是某一最長路的一頭 
void finddep(int u, int pre ){ 
    dep[u] = dep[pre] + 1;
    p[u] = pre;
    for(int i = head[u];i != -1; i = edge[i].next) {
        int to = edge[i].to;
        if(to == pre)   continue;
        finddep(to, u);
    }
}

int max(int a, int b ){
    return a>b?a:b;
}
// dp[u][0]表示該節點到子樹中的最長路，dp[u][1]表示次長路 ， dp[u][2]表示該節點這顆樹中的最長路
void cal(int u, int pre) {
    dp[u][0] = dp[u][1] = dp[u][2] = 0;
    for(int i = head[u];i != -1;i = edge[i].next) {
        int to = edge[i].to;
        if(to == pre)   continue;
        cal(to, u);
        int now = dp[to][0] + 1;
        if(now >= dp[u][0]) {
            dp[u][1] = dp[u][0];
            dp[u][0] = now;
        }else if(now > dp[u][1])
            dp[u][1] = now;
        dp[u][2] = max(dp[u][2], dp[to][2]);
    }
    dp[u][2] = max(dp[u][2] , dp[u][1] + dp[u][0]);
//    printf("%d %d\n", u, dp[u][2]);
}

int mxlen; // 整棵樹求出的最長路

void dfs(int u, int pre) {
    for(int i = head[u];i != -1;i = edge[i].next) {
        int to = edge[i].to;
        int val = edge[i].val;
        int id = edge[i].id;
        if(to == pre)   continue;
        dfs(to, u);
        if(vis[u] && vis[to])  //邊在最長路上
            ee[id] = max(ee[id], val*dp[to][2]);
        else 
            ee[id] = val*mxlen;　//邊不在最長路上
    }
}

int main() {
    int n, i, j, u, to, val;
    int t, cas = 1;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        init(n);
        for(i = 1;i <= n-1; i++) {
            scanf("%d%d%d", &u, &to, &val);
            newedge(u, to, val, i);
            newedge(to, u, val, i);
        }
        dep[0] = -1;
        finddep(1, 0);
        u = 1;
        for(i = 1;i <= n; i++) if(dep[i] > dep[u])
            u = i;
        finddep(u, 0);
        to = 1;
        for(i = 1;i <= n; i++) if(dep[i] > dep[to])
            to = i;
        // u ， to為最長路的兩頭
        for(i = 1;i <= n; i++)  vis[i] = 0;
        int cur = to;
        while(cur != 0) {
            vis[cur] = 1;
            cur = p[cur];
        }
        mxlen = dep[to];
        for(i = 1;i <= n-1; i++)    ee[i] = 0;
        // 雙向都dfs一遍
        cal(u, -1);
        dfs(u, -1);
        cal(to, -1);
        dfs(to, -1);
        int ans = 1;
        for(i = 1;i <= n-1; i++) if(ee[i] < ee[ans])
            ans = i;
        printf("Case #%d: %d\n", cas++, ans);
    }
    return 0;
}