CodeForces-1076E Vasya and a Tree

Problem Description:

Vasya has a tree consisting of n vertices with root in vertex 1. At first all vertices has 0 written on it.

Let d(i,j) be the distance between vertices i and j, i.e. number of edges in the shortest path from i to j. Also, let's denote k-subtree of vertex x — set of vertices y such that next two conditions are met:

 　　x is the ancestor of y (each vertex is the ancestor of itself);

　　 d(x,y)≤k.

Vasya needs you to process m queries. The i-th query is a triple vi, di and xi. For each query Vasya adds value xi to each vertex from di-subtree of vi.

Report to Vasya all values, written on vertices of the tree after processing all queries.

Input:

The first line contains single integer n (1≤n≤3⋅105) — number of vertices in the tree.

Each of next n−1 lines contains two integers x and y (1≤x,y≤n) — edge between vertices x and y. It is guarantied that given graph is a tree.

Next line contains single integer m (1≤m≤3⋅105) — number of queries.

Each of next m lines contains three integers vi, di, xi (1≤vi≤n, 0≤di≤109, 1≤xi≤109) — description of the i-th query.

Output:

Print n integers. The i-th integers is the value, written in the i-th vertex after processing all queries.

　　这道题是个树上查分应该是比较好看出来的(尽管我看了很久)，差分我就不YY了，主要是用什么来维护区间修改。

　　方法也是比较多的，有大佬再加了一个差分（详见 gushui博客），也有大佬用树状数组（详见 zqs博客），更有大佬用线段树（这位大佬没有写博客，所以没有链接）。但是，差分和树状数组都要跑两边DFS，还要二分一下，线段树码量大，而且以上方法都带log，是O(n log n)的。

　　下面我来YY一哈O(n)的线性做法：

　　首先读入图和询问，然后我们开始DFS，需要记一个类似于Lasy标记的东西（Code中的V[]），可以求出Ans(详见代码)。

　　（"O2+O3+fread" 跑得飞快，200ms）

　　Code:

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#include<bits/stdc++.h>

using namespace std;

int n,m,Deep[300005],Cnt,Head[300005],Next[600005],To[600005];

long long V[300005],Ans[300005];

struct node {int Deep,V;}A[300005];

vector<node>Q[300005];

#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,65536,stdin),p1==p2)?EOF:*p1++)

char buf[65536],*p1,*p2;

inline int read()

{

    char ch;int x(0);

    while((ch=gc)<48);

    do x=x*10+ch-48;while((ch=gc)>=48);

    return x;

}

inline void ADD(int x,int y) {Next[++Cnt]=Head[x],Head[x]=Cnt,To[Cnt]=y,Next[++Cnt]=Head[y],Head[y]=Cnt,To[Cnt]=x;}

inline void DFS(int x,int fa,long long Sum)

{

    Sum+=V[Deep[x]];

    for(register int i=0;i<(int)Q[x].size();++i)

    {

        Sum+=Q[x][i].V;

        if(Deep[x]+Q[x][i].Deep+1<=n) V[Deep[x]+Q[x][i].Deep+1]-=Q[x][i].V;

    }

    Ans[x]=Sum;

    for(register int i=Head[x],j;i;i=Next[i])

    {

        j=To[i];

        if(j==fa) continue;

        Deep[j]=Deep[x]+1,DFS(j,x,Sum);

    }

    for(register int i=0;i<(int)Q[x].size();++i)

        if(Deep[x]+Q[x][i].Deep+1<=n) V[Deep[x]+Q[x][i].Deep+1]+=Q[x][i].V;

}

int main()

{

    n=read();

    for(register int i=1,x,y;i<n;++i) x=read(),y=read(),ADD(x,y);

    m=read();

    for(register int i=1,x,y,z;i<=m;++i) x=read(),y=read(),z=read(),Q[x].push_back(node{y,z});

    Deep[1]=1,DFS(1,0,0);

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

    return 0;

}

巴特西

CodeForces-1076E Vasya and a Tree

最新文章

热门文章