【树形DP】POJ.1985 Cow Marathon

题链

https://vjudge.net/problem/POJ-1985

题解

0. 求树的直径，边权都为正，输出直径的值
1. 假设树以 1 为根
2. 以 u 为根，最长直径要么是经过 u 节点的，要么是在 u 节点的某个子树底下
3. 设 dp[u] 表示 u 的子树从 u 开始往下走到某个叶子最远能走多远
   • dp[u] = max(dp[vi] + dis(u, v));
4. 对于 节点 u :
   • ans = max( ans, dp[vi] + dp[vj] + dis(u, vi) + dis(u, vj) );
   • vi 和 vj 是 u 的某两个不同的孩子节点
5. 于是可以先 dfs 到底，dp[u] + dp[v] + dis(u, v) 的方式更新 ans
   • 因为 dp[u] 是遍历到 v 孩子之前更新到的最长链路了

代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MS 40009
#define LL long long 

int n, m, k;
struct node{
    int poi, cost;
};
vector<node > vc[MS];
int dp[MS];
int ans;

void dfs(int u, int fa){
    for(int i=0;i<(int)vc[u].size();i++){
        node nb = vc[u][i];
        int v = nb.poi;
        int c = nb.cost;
        if(v == fa) continue;
        dfs(v, u);
        ans = max(ans, dp[u] + dp[v] + c);
        dp[u] = max(dp[u], dp[v] + c);
    }
}

void solve(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int u, v, w; char c; cin >> u >> v >> w >> c;
        node tmp; tmp.cost = w;
        tmp.poi = v, vc[u].push_back(tmp);
        tmp.poi = u, vc[v].push_back(tmp);
    }
    dfs(1, 0);
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    int ce = 1;
    while(ce--) solve();
    
    return 0;
}