这是一个静态问题
按DFS走，进入一个子树时把子树根上挂的修改激活，离开子树时撤销
这样所有的修改和查询都是对于深度的
QvQ：递归三参数栈爆炸了
#include
using namespace std;
#define M 524288
#define N 300005
typedef long long ll;
int L,R,aim,n,m,tot,s[N],dep;
ll t[M<<1],ans,op[N];
vector【Codeforces 1076E E. Vasya and a Tree】 > q[N];
struct edge{int v,n;
}e[N<<1];
#define Push(u,v) push(u,v),push(v,u)
inline void push(int u,int v){e[++tot]=(edge){v,s[u]};
s[u]=tot;
}void change(int k,int l,int r)
{
if (L<=l && r<=R){t[k]+=aim;
return;
}
int mid=l+r>>1;
if (L<=mid) change(k<<1,l,mid);
if (mid>1;
if (aim<=mid) find(k<<1,l,mid);
else find(k<<1|1,mid+1,r);
}void dfs(int k,int f)
{
dep++;
for (auto s:q[k])
{
L=dep;
R=dep+s.first;
aim=s.second;
change(1,1,M);
}
aim=dep;
ans=0;
find(1,1,M);
op[k]=ans;
for (int i=s[k];
i;
i=e[i].n) if (e[i].v!=f) dfs(e[i].v,k);
for (auto s:q[k])
{
L=dep;
R=dep+s.first;
aim=-s.second;
change(1,1,M);
}
dep--;
}int main()
{
scanf("%d",&n);
for (int i=1,u,v;
i 推荐阅读
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- 题库-CF|【Codeforces Round 370 (Div 2) E】【线段树 等比数列 区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- Codeforces|Codeforces Round #643 (Div. 2) B.Young Explorers