BZOJ 1060: [ZJOI2007]时态同步 – [树形DP]


题目传送门(BZOJ)
>原文链接<

题解 :

状态 :F[p]为点p到自己的所有叶子的最长时间。

转移 :F[p] = \max{F[to[i]]+val[i]}

在求得每个点的F之后,再把\sum(F[p]-F[to[i] – val[i])累加在答案上即可。

非常简单的树形DP

代码 :

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1001010;
long long f[N];
struct Edge {
    int to, val;
    Edge *next;
}*h[N], e[N<<1];
int _;
inline char Nc() {
    static char Buf[100000], *p1, *p2;
    return p1==p2&&(p2=(p1=Buf)+fread(Buf, 1, 100000, stdin), p1==p2)?EOF:*p1++;
}
int Rd() {
    int x = 0;char c = Nc();
    while(!isdigit(c)) c=Nc();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=Nc();
    return x;
}
void Add_Edge(int u, int v, int w) {
    Edge *tmp = &e[++_];
    tmp->to = v;
    tmp->val = w;
    tmp->next = h[u];
    h[u] = tmp;
    tmp = &e[++_];
    tmp->to = u;
    tmp->val = w;
    tmp->next = h[v];
    h[v] = tmp;
}
long long ans = 0;
void Dfs1(int p, int fa) {
    long long now = 0;
    for(Edge *i = h[p]; i; i = i->next) {
        if(i->to!=fa) {
            Dfs1(i->to, p);
            now = max(now, f[i->to]+i->val);
        }
    }
    f[p] = now;
    for(Edge *i = h[p]; i; i = i->next) {
        if(i->to!=fa) {
            ans += now-(f[i->to]+i->val);
        }
    }
}
int main() {
    int n = Rd(), s = Rd();
    for(int i = 2; i <= n; i ++ ) {
        int u = Rd(), v = Rd(), w = Rd();
        Add_Edge(u, v, w);
    }
    Dfs1(s, 0);
    printf("%lld\n", ans);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注