ZSTU 4248 KI的目标（dfs）

KI的目标

Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 308 Solved: 77

Description

KI给自己制定了最近制定了一些学习目标，因为有些大目标的达到要先完成一些小目标，所以KI就下意识的把这些目标连成了一棵树，以1号目标为根。

KI是个很谨慎的人，于是他请他的朋友们对这棵树上的每条边评估了一个努力值cost(i)，并对每个目标评估了一个

价值val(i)。

然后KI决定去掉树上的一些不可行的目标，他判断的依据是：

假设目标v属于以u为根的子树，如果dis(u,v)<val(u)-val(v),那么以v为根的整棵子树都会被去掉。(dis(u,v)从节点u到节点v所有边的边权和)

请帮KI计算一下最后他还剩下几个目标。

Input

第一行有个整数T, 表示测试组数。T≦101。

接下来每个测试组，第一行给出一个数n, 表示当前这棵树的节点数。

接下来n-1行，每行有两个数x y cost:表示x个节点和y节点间有条边, 这条边的努力值为cost。

接下来一行，有n个数，第i个数表示val(i)。

1 <= x,y <= n <= 100000, -1e9 <= try(i),val(i) <= 1e9

Output

对于每个测试组，把对应的答案在一行中输出。

Sample Input

1

6

1 2 1

2 3 5

2 4 -10

1 5 3

5 6 4

6 5 4 5 3 6

Sample Output

HINT

Source

假设目标v属于以u为根的子树，如果dis(u,v)<val(u)-val(v),那么以v为根的整棵子树都会被去掉。

我们假设$dist(n)$为从$1$号根节点出发走到$n$号节点时经过的边的边权总和。

那么，要使$dis(u,v)<val(u)-val(v)$,

则$dist(v)-dist(u)<val(u)-val(v)$,

即$dist(v)+val(v)<dist(u)+val(u)$.

那么就很明显了，跑一遍DFS计算出$dist(i)+val(i)$再根据题目信息更新答案即可。

#include <bits/stdc++.h>

using namespace std;

#define rep(i,a,b)      for(int i(a); i <= (b); ++i)

#define for_edge(i,x)   for(int i = H[x]; i; i = X[i])

#define LL          long long

const int N = 100010;

int E[N << 1], H[N << 1], X[N << 1], vis[N], f[N], fa[N], fl[N];

int x, y, T, n, et, ans;

LL V[N << 1], a[N], c[N], dist[N], val;

inline void addedge(int a, int b, LL c){

    E[++et] = b, X[et] = H[a], H[a] = et, V[et] = c;

    E[++et] = a, X[et] = H[b], H[b] = et, V[et] = c;

}

void dfs(int x, LL num){

    vis[x] = 1; dist[x] = num;

    for_edge(i, x){

        int v = E[i];

        if (!vis[v]){

            fa[v] = x;

            dfs(v, num + V[i]);

        }

    }

}

void work(int x){

    vis[x] = 1; fl[x] = 0;

    for_edge(i, x){

        int v = E[i];

        if (v != fa[x]){ if (!vis[v]) work(v); }

    }

}

int main(){

    scanf("%d", &T);

    while (T--){

        scanf("%d", &n);

        et = 0;

        memset(H, 0, sizeof H);

        rep(i, 1, n - 1){

            scanf("%d%d%lld", &x, &y, &val);

            addedge(x, y, val);

        }

        rep(i, 1, n) scanf("%lld", a + i);

        memset(vis, 0, sizeof vis);

        dfs(1, 0);

        rep(i, 1, n) c[i] = a[i] + dist[i], fl[i] = 1;

        memset(f, 0, sizeof f);

        rep(i, 2, n) if (c[i] < c[fa[i]]) f[i] = 1;

        memset(vis, 0, sizeof vis);

        rep(i, 1, n) if (f[i] && vis[i] == 0)  work(i);

        ans = 0;

        rep(i, 1, n) ans += fl[i];

        printf("%d\n", ans);    

    }

    return 0;

}

巴特西