跳转至

BZOJ1060 时态同步

题解

水一发系列

水题，除了水一发之外 没什么太多好讲的。

题目要求你通过对某些边加边权使得每个点的所有儿子节点到叶子节点的距离都相同。

每个点维护到叶子节点的最长链，dfs更新一下然后计算答案就行。

程序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#define MAX_N 500007
typedef long long ll;

int N, S;
int head[MAX_N], to[MAX_N * 2], nxt[MAX_N * 2], cap;
ll dis[MAX_N * 2];
ll mx[MAX_N], res;

inline ll read () {
    ll x = 0;
    char c = getchar();
    while (c < '0' || '9' < c)
        c = getchar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x;
}

void addEdge (int u, int v, ll w) {
    nxt[++cap] = head[u];
    head[u] = cap;
    to[cap] = v;
    dis[cap] = w;
}

void dfs (int x, int fa) {
    for (int i = head[x]; i; i = nxt[i]) 
        if (to[i] != fa) {
            dfs(to[i], x);
            mx[x] = std::max(mx[x], mx[to[i]] + dis[i]);
        }
    for (int i = head[x]; i; i = nxt[i])
        if (to[i] != fa) {
            res += mx[x] - mx[to[i]] - dis[i];
        }
}

int main () {
    N = read(), S = read();
    int u, v;
    ll w;
    for (int i = 1;i < N; ++i)
        u = read(), v = read(), w = read(), addEdge(u, v, w), addEdge(v, u, w);
    dfs(S, 0);
    printf("%lld\n", res);
    return 0;
}