2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016) F dfs序,树状数组

2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016)

题意：一棵树，每个点有一个优先级和权值，每个点必须在它的子树中小于它的优先级的点执行后才可执行，求每个点的执行时间。

tags：就是跑dfs序，套个树状数组。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,b,a) for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define fi  first
#define se  second
typedef long long ll;
const int N = 100005;

int n, root, mx;
ll ans[N], tr[N];
vector<int >G[N];
pair<int , int > p[N];
void add(int x, int y) { for(; x<=mx; tr[x]+=y, x+=x&-x); }
ll query(int x) { ll sum=0; for(; x>0; sum+=tr[x], x-=x&-x); return sum; }
void dfs(int u, int fa)
{
    ll s1=query(p[u].fi-1);
    for(int i=0; i<G[u].size(); ++i)  {
        int v=G[u][i];
        if(v!=fa) dfs(v, u);
    }
    ans[u]=query(p[u].fi-1)-s1;
    add(p[u].fi, p[u].se);
}
int main()
{
    scanf("%d", &n);
    int pi;
    rep(i,1,n) {
        scanf("%d %d %d", &pi, &p[i].fi, &p[i].se);
        mx=max(p[i].fi, mx);
        if(pi==-1) root=i;
        else G[i].push_back(pi), G[pi].push_back(i);
    }
    dfs(root, 0);
    rep(i,1,n) printf("%lld
", ans[i]);

    return 0;
}