GYM - 101147 J.Whistle's New Car

题意：

　　给出一颗有点权和边权的树。求每一个点u的子树中有多少点v，使得点v到点u的距离小于等于点v的权值。

题解：

　　对于每一个点，倍增的预处理出他的祖宗节点及距离。根据预处理的结果求出每个点能到的最远的祖宗节点。

　　设点u能到的最远祖宗节点为v。利用差分的思想在点tree[u]+1，点tree[v]-1。

　　最后每个点的答案就是子树的tree[]和。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 5e5+;

int t, n, u, v, tree[maxn], ans[maxn];

ll c, x[maxn];

struct node {

    ll val; int nod;

};

node fa[][maxn], tmp;

vector<node> g[maxn];

void dfs(int u, int pre) {

    fa[][u].nod = pre;

    int len = g[u].size();

    for(int i = ; i < len; i++) {

        int v = g[u][i].nod;

        if(v==pre) {

            fa[][u].val = g[u][i].val;

            continue;

        }

        dfs(v, u);

    }

}

void dfs_double(int u, int pre) {

    int len = g[u].size();

    for(int i = ; i < len; i++) {

        int v = g[u][i].nod;

        if(v==pre) continue;

        dfs_double(v, u);

    }

    tree[u]++;

    ll tv = x[u];

    for(int k = ; k >= ; k--) {

        if(fa[k][u].val <= tv) {

            tv -= fa[k][u].val;

            u = fa[k][u].nod;

        }

    }

    tree[u]--;

}

void solve(int u, int pre) {

    int len = g[u].size();

    for(int i = ; i < len; i++) {

        int v = g[u][i].nod;

        if(v==pre) continue;

        solve(v, u);

    }

    for(int i = ; i < len; i++) {

        int v = g[u][i].nod;

        if(v==pre) continue;

        ans[u] += tree[v]+ans[v];

    }

}

int main() {

    freopen("car.in","r",stdin);

    scanf("%d", &t);

    while(t--) {

        scanf("%d", &n);

        memset(tree, , sizeof(tree));

        memset(ans, , sizeof(ans));

        for(int i = ; i <= n; i++) g[i].clear();

        for(int i = ; i <= n; i++) scanf("%lld", &x[i]);

        for(int i = ; i < n; i++) {

            scanf("%d%d%lld", &u, &v, &tmp.val);

            tmp.nod = v;

            g[u].push_back(tmp);

            tmp.nod = u;

            g[v].push_back(tmp);

        }

        dfs(, );

        for(int k = ; k < ; k++) {

            for(int v = ; v <= n; v++) {

                fa[k+][v].nod = fa[k][fa[k][v].nod].nod;

                fa[k+][v].val = fa[k][v].val+fa[k][fa[k][v].nod].val;

            }

        }

        dfs_double(, );

        solve(, );

        for(int i = ; i <= n; i++) {

            printf("%d", ans[i]);

            if(i==n) puts("");

            else printf(" ");

        }

    }

}

巴特西

GYM - 101147 J.Whistle's New Car

最新文章

热门文章