1. 首页
2. 树状数组
3. 本页

UVALive 7649 Performance Review (树状数组)

题意：~

思路：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <class T> inline bool scan_d(T &ret) {char c; int sgn;if(c=getchar(),c==EOF) return 0;while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn;return 1;}
int n;
const int N = 100050;
struct mmp {
    int v, next;
} edge[N];
int head[N], tot;
void add(int u, int v)
{
    edge[tot] = {v, head[u]};
    head[u] = tot++;
}
LL val[N];
LL ans[N], sum[N];
int lev[N];

void init()
{
    memset(head, -1, sizeof(head));
    tot = 0;
    memset(ans, 0, sizeof(ans));
    memset(sum, 0, sizeof(sum));
}

void update(int x, LL val)
{
    for(int i = x; i < N; i += i & (-i))
    {
        sum[i] += val;
    }
}

LL query(int x)
{
    LL res = 0;
    for(int i = x; i > 0; i -= i & (-i))
    {
        res += sum[i];
    }
    return res;
}

void dfs(int u)
{
    LL pre = query(lev[u] - 1);
    update(lev[u], val[u]);
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        dfs(v);
    }
    ans[u] = query(lev[u] - 1) - pre;
}

int main()
{
    while(~scanf("%d", &n))
    {
        init();
        int u, k, w;
        int rt = 0;
        for(int i = 1; i <= n; ++i)
        {
            scan_d(u), scan_d(k), scan_d(w);
            lev[i] = k;
            val[i] = w;
            if(u == -1) rt = i;
            else add(u, i);
        }
        dfs(rt);
        for(int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
    }
    return 0;
}