E. Vasya and a Treetime (思维+数据结构)

原题链接

解题思路：

是对子树的操作，容易想到dfs序，但又是对深度小于等于k的子树操作，在dfs序中不是连续的，如果考虑bfs序，深度是递增的，但是连续的段又不满足是子树，也不行。

本题的特点是查询只有一次，故可以离线，对于任意一个点，只有他的所有父会产生影响，还是考虑dfs ，这样每遍历一个点他的所有父一定已经访问过了，用数据结构维护一个深度段（树状数组，线段树都可），每访问到一个点，把他的操作全做一边，（区间加操作，经典差分）。此时，这个点的答案直接在数据结构里查询就可以。（影响他的点已经全操作过了）

仅仅这样还有一个问题，数据结构维护的是深度，每次子树访问结束时，要回退所有操作。（举个最简单的例子，根结点的左右子树有相同的深度，如果不回退就会产生影响）

Code:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
#define guo312 std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define Inf LONG_LONG_MAX
#define inf INT_MAX
#define endl "n"
#define PI 3.1415926535898
using namespace std;
const int N=3e5+10;
int n,m;
vector ve1[N];
vector> ve2[N];
ll ans[N],c[N];
int lowbit(int x){
	return x&(-x);
}

void add(int x,int num){
	for( ;x<=n;c[x]+=num,x+=lowbit(x));	
}

ll query(int x){
	ll re=0;
	for( ;x>0;re+=c[x],x-=lowbit(x));
	return re;
}

void dfs(int u,int fa,int dep){
	for(auto it:ve2[u]){
		add(dep,it.second);
		add(dep+it.first+1,-it.second);	
	}	
	ans[u]=query(dep);
	for(auto it:ve1[u]){
		if(it!=fa){
			dfs(it,u,dep+1);
		}
	}
	for(auto it:ve2[u]){
		add(dep,-it.second);
		add(dep+it.first+1,it.second);
	}
}

int main(){
guo312;
	cin>>n;
	for(int i=1;i>s1>>s2;
		ve1[s1].push_back(s2);
		ve1[s2].push_back(s1);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int s1,s2,s3; cin>>s1>>s2>>s3;
		ve2[s1].push_back({s2,s3});
	}
	dfs(1,0,1);
	for(int i=1;i<=n;i++){
		cout<

E. Vasya and a Treetime (思维+数据结构)

C/C++/C#相关栏目本月热门文章