Educational Codeforces Round 54 E. Vasya and a Tree 트리의 접두어 및 트리 배열

문서 목록

Educational Codeforces Round 54 E. Vasya and a Tree

트리 접두어 및

수상수조

분석

Educational Codeforces Round 54 E. Vasya and a Tree
트리 접두어 및

#include 
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define  FI first
#define  SE second
#define rep(i,a,n) for (int i=a;i
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<LL,LL> P;
const int maxn = 3e5+100;
LL add[maxn];
LL res[maxn];
vector<LL> G[maxn];
vector<P> command[maxn];
int n,m;
void dfs(int node,int h,int fa,LL sum){
    for(auto c: command[node])
    {
        int l = h,r = l + c.first;
        add[l] += c.second;
        if(r+1 <= n)
            add[r+1] -= c.second;
    }
    sum += add[h];
    res[node] = sum;
    for(auto c: G[node]){
        if(c == fa) continue;
        dfs(c,h+1,node,sum);
    }
    sum -= add[h];
    for(auto c: command[node])
    {
        int l = h,r = l + c.first;
        add[l] -= c.second;
        if(r+1 <= n)
            add[r+1] += c.second;
    }
}
int main(void)
{  
    cin>>n;
    for(int i = 0,v,u;i < n-1; ++i){
        scanf("%d%d",&v,&u);
        G[v].Pb(u);
        G[u].Pb(v);
    }
    cin>>m;
    for(int i = 0,v,h,x;i < m; ++i){
        scanf("%d%d%d",&v,&h,&x);
        command[v].Pb(P(h,x));
    }
    dfs(1,0,-1,0);

    for(int i = 1;i <= n; ++i)
        printf("%lld%c",res[i]," 
"[i==n]);
        

    return 0;
}

트리 배열
분석하다.
//만약에 우리가 dfs 서열을 통해 u 노드에 들어간다고 가정하면 우리는 이 노드에 대한 기여를 모두 더하고 구간 수정에 해당한다. 트리 수조의 노드는 깊이//이 노드를 나갈 때 u노드의 영향을 줄인다. u 노드가 다른 노드에 기여하지 않았기 때문이다//트리 수조는 접두사와 맞기 때문에 우리 구간을 수정할 때 수정한 구간이다. [l,l+h]. 우리는 사실 수정이라고 할 수 있다[1,l+h].이렇게 해도 [l+h+1,n]에 영향을 미치지 않기 때문에//그래서 깊이를 모두 반대로 할 수 있다

#include 
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define  FI first
#define  SE second
#define rep(i,a,n) for (int i=a;i
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> Pii;
typedef pair<LL,LL> PLL;
const int maxn = 3e5+100;
LL tree[maxn];//    

void Add(int x,int p){
    x++;
    while(x < maxn){
        tree[x] += p;
        x += lowbit(x);
    }
}
LL Sum(int x){
    LL ans = 0;
    x++;
    while(x > 0){
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
LL depth[maxn];
int id[maxn];// id[i]     i dfs 
int vs[maxn];// vs[i]   dfs  i     
int ed[maxn];//         dfs 

LL ans[maxn];
std::vector<int> G[maxn];
std::vector<PLL> Q[maxn];
int k = 0;
void dfs(int node,int fa){
    id[node] = ++k;
    vs[k] = node;
    // depth[node] = d;/
    for(auto c: G[node]){
        if(c == fa) continue;
        depth[c] = depth[node]+1;
        dfs(c,node);
    }
    ed[node] = k;
}
int main(void)
{
    int n;
    cin>>n;
    for(int i = 2;i <= n; ++i){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].Pb(v);
        G[v].Pb(u);
    }
    depth[1] = 1;
    dfs(1,-1);
    int m;
    cin>>m;
    for(int i = 1;i <= m; ++i){
        LL u,d,v;
        scanf("%lld%lld%lld",&u,&d,&v);
        Q[id[u]].Pb(PLL(min(depth[u]+d,(LL)n),v));
        Q[ed[u]+1].Pb(PLL(min(depth[u]+d,(LL)n),-v));
    }
    for(int i= 1;i <= n; ++i){
        for(auto c: Q[i]){
            Add(n-c.first,c.second);
        }
        ans[vs[i]] = Sum(n-depth[vs[i]]);
    }
    for(int i = 1;i <= n; ++i)
        cout<<ans[i]<<" ";
    

   return 0;
}