CF1076E：Vasya and a Tree

浅谈树状数组与线段树：https://www.cnblogs.com/AKMer/p/9946944.html

题目传送门：https://codeforces.com/problemset/problem/1076/E

因为询问只有一次，所以我们可以考虑怎样快速的找出会影响当前点的操作。

因为只有祖先结点上的操作可能会影响当前结点，所以我们在\(dfs\)的时候用树状数组动态维护深度差分值，然后单点询问当前深度应该增加多少就行了。如果本子树处理完了，那么就把差分去掉，以免影响其它子树。

时间复杂度：\(O(mlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <vector>

using namespace std;

typedef long long ll;

#define low(i) ((i)&(-i))

const int maxn=3e5+5;

int n,m,tot;

ll val[maxn];

int dep[maxn];

int now[maxn],pre[maxn*2],son[maxn*2];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct query {

	int v,d;

	query() {}

	query(int _v,int _d) {

		v=_v,d=_d;

	}

};

vector<query>s[maxn];

struct TreeArray {

	ll c[maxn];

	void add(int pos,int v) {

		for(int i=pos;i<=n;i+=low(i))

			c[i]+=v;

	}

	ll query(int pos) {

		ll res=0;

		for(int i=pos;i;i-=low(i))

			res+=c[i];

		return res;

	}

}T;

void add(int a,int b) {

	pre[++tot]=now[a];

	now[a]=tot;son[tot]=b;

}

void dfs(int fa,int u) {

	dep[u]=dep[fa]+1;

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(v!=fa)dfs(u,v);

}

void make_ans(int fa,int u) {

	vector<query>::iterator it;

	for(it=s[u].begin();it!=s[u].end();it++) {

		int l=dep[u],r=(*it).d+dep[u];r=min(r,n);

		T.add(l,(*it).v);T.add(r+1,-(*it).v);

	}val[u]=T.query(dep[u]);//进来的时候差分

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(v!=fa)make_ans(u,v);

	for(it=s[u].begin();it!=s[u].end();it++) {

		int l=dep[u],r=(*it).d+dep[u];r=min(r,n);

		T.add(l,-(*it).v);T.add(r+1,(*it).v);

	}//出去的时候反差分

}

int main() {

	n=read();

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

		int a=read(),b=read();

		add(a,b);add(b,a);

	}dfs(0,1);m=read();

	for(int i=1;i<=m;i++) {

		int u=read(),d=read(),x=read();

		s[u].push_back(query(x,d));

	}

	make_ans(0,1);

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

	printf("%lld ",val[i]);

	return 0;

}

巴特西

CF1076E：Vasya and a Tree

最新文章

热门文章