Problem Specification Value
Time Limit 10 Sec
Memory Limit 162 MB
Submit 2130
Solved 613

Description

小 Q 在电子工艺实习课上学习焊接电路板. 一块电路板由若干个元件组成, 我们不妨称之为节点, 并将其用数字 1, 2, 3...... 进行标号. 电路板的各个节点由若干不相交的导线相连接, 且对于电路板的任何两个节点, 都存在且仅存在一条通路 (通路指连接两个元件的导线序列). 在电路板上存在一个特殊的元件称为 “激发器”. 当激发器工作后, 产生一个激励电流, 通过导线传向每一个它所连接的节点. 而中间节点接收到激励电流后, 得到信息, 并将该激励电流传向与它连接并且尚未接收到激励电流的节点. 最终, 激烈电流将到达一些 “终止节点”--接收激励电流之后不再转发的节点. 激励电流在导线上的传播是需要花费时间的, 对于每条边 e, 激励电流通过它需要的时间为 te, 而节点接收到激励电流后的转发可以认为是在瞬间完成的. 现在这块电路板要求每一个 “终止节点” 同时得到激励电路--即保持时态同步. 由于当前的构造并不符合时态同步的要求, 故需要通过改变连接线的构造. 目前小 Q 有一个道具, 使用一次该道具, 可以使得激励电流通过某条连接导线的时间增加一个单位. 请问小 Q 最少使用多少次道具才可使得所有的 “终止节点” 时态同步?

Input

第一行包含一个正整数 N, 表示电路板中节点的个数. 第二行包含一个整数 S, 为该电路板的激发器的编号. 接下来 N-1 行, 每行三个整数 a, b, t. 表示该条导线连接节点 a 与节点 b, 且激励电流通过这条导线需要 t 个单位时间

Output

仅包含一个整数 V, 为小 Q 最少使用的道具次数

Sample Input

3
1
1 2 1
1 3 3

Sample Output

2

HINT

N ≤ 500000, te ≤ 1000000

Source

巨水树形 DP, 局部子树具有贪心决策单调性, 可以贪心子树的权值.

然后就没有什么可说的了...... 看一下代码, 里面的注释还有一些内容.


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long ll;
const int maxn = 500100;

int n, S;
ll  res = 0;

class Graph
{
public:
    struct edge { int u, v, len; edge *next; };
    edge *edges[maxn], epool[2 * maxn];
    int cnt, root;
    int par[maxn];
    ll  dp[maxn];
    void addedge(int u, int v, int len)
    {
        edge *p = &epool[cnt++], *q = &epool[cnt++];
        p->u = u; p->v = v; p->len = len;
            p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u; q->len = len;
            q->next = edges[v]; edges[v] = q;
        return ;
    }
    void dfs(int p)
    {
        dp[p] = 0;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (ep->v != par[p]) {
                par[ep->v] = p;
                dfs(ep->v);
                dp[p] = max(dp[p], dp[ep->v] + ep->len);
            }
        return ;
    }
    void prepare_graph(int _root)
    {
        root = _root;
        par[root] = 0;
        dfs(root);
        return ;
    }
    void work_dp(int p)
    {
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (par[p] != ep->v) {
                res += dp[p] - (dp[ep->v] + ep->len);
                work_dp(ep->v);
            }
        return ;
    }
} graph;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &S);
    for (int i = 1, a, b, c; i < n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        graph.addedge(a, b, c);
    }
    graph.prepare_graph(S);
    // Done preparing, now we have a theorem:
    //     It is best to do the work on a parent instead of children.
    //     For the children it must cost much more than parents...
    //     Therefore the theorem is proven.
    graph.work_dp(S);
    printf("%lld\n", res);
    return 0;
}
from pydatagen import *
from math import *
n = randrange(100000, 500000)
s = randrange(1, n + 1)
g = Tree(n, maxchildren=int(sqrt(n)), weighed=True, weight_range=range(1, 1000000))
printf('%d %d\n' % (n, s))
print_oi(g)