E. Vasya and a Tree(回溯+树上差分)

第一眼感觉是树剖裸体,刚想复制模板

发现是修改这个k-subtree

那不可做了啊,我树剖模板都是靠套的…

$好在不需要树剖,建立一颗以深度为下标的树状数组$

$直接从根往下dfs,遍历到u时,由于u的操作只会影响子树$

$我们直接选择用树状数组差分$

$在deep[u]++,在deep[u+d+1]--$

$由于dfs只会在子树中进行,所以有深度相同的多个点也没事$

$反正最后都会先遍历某棵子树,回溯的时候抹掉这个操作就好了$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
int n,m,sumn[maxn+10];
vector<int>vec[maxn+10];
vector< pair<int,int> >q[maxn+10];
int lowbit(int x){return x&(-x);
}
void add(int x,int k){for(;x<=3e5;x+=lowbit(x) )	sumn[x]+=k;
}
ll ask(int x){ll ans=0;for(;x;x-=lowbit(x) )	ans+=sumn[x];return ans;
}
ll ans[maxn+10];
void dfs(int u,int deep,int fa)
{for(int i=0;i<q[u].size();i++)//遍历所有关于u的询问{pair<int,int> w=q[u][i]; add(deep,w.second);add(deep+w.first+1,-w.second);	//差分的思想 }ans[ u ]=ask( deep );for(int i=0;i<vec[u].size();i++){int v=vec[u][i];if( v==fa )	continue;dfs(v,deep+1,u);	}//下面是回溯,这颗子树处理完了,清空这个子树的影响 for(int i=0;i<q[u].size();i++)//遍历所有关于u的询问{pair<int,int> w=q[u][i]; add(deep,-w.second);add(deep+w.first+1,w.second);	//差分的思想 }
}
int main()
{cin >> n;for(int i=1,l,r;i<n;i++){scanf("%d%d",&l,&r);vec[l].push_back(r);vec[r].push_back(l);}cin >> m;for(int i=1;i<=m;i++){int v,d,x;scanf("%d%d%d",&v,&d,&x);q[v].push_back( make_pair(d,x) );}dfs(1,1,0);for(int i=1;i<=n;i++)printf("%d ",ans[i]);
}