【BZOJ3589】动态树 题解
BZOJ权限题，这里给一下题面：
Description
别忘了这是一棵动态树, 每时每刻都是动态的。 小明要求你在这棵树上维护两种事件：
事件0:
这棵树长出了一些果子, 即某个子树中的每个节点都会长出K个果子。
事件1:
小明希望你求出几条树枝上的果子数。 一条树枝其实就是一个从某个节点到根的路径的一段。 每次小明会选定一些树枝, 让你求出在这些树枝上的节点的果子数的和。
注意, 树枝之间可能会重合, 这时重合的部分的节点的果子只要算一次。
Input
第一行一个整数n(1≤n≤200,000), 即节点数。
接下来n−1行，每行两个数字u,v。 表示果子u和果子v之间有一条直接的边。节点从11开始编号。
在接下来一个整数nQ(1≤nQ≤200,000), 表示事件。
最后nQ行，每行开头要么是0，要么是1。
如果是0, 表示这个事件是事件0。 这行接下来的2个整数u,delta表示以u为根的子树中的每个节点长出了delta个果子。
如果是1, 表示这个事件是事件11。 这行接下来一个整数K(1≤K≤5), 表示这次询问涉及KK个树枝。 接下来K对整数uk,vk每个树枝从节点uk到节点vk。 由于果子数可能非常多, 请输出这个数模2^31的结果。
Output
对于每个事件1, 输出询问的果子数。
Sample Input
5
1 2
2 3
2 4
1 5
3
0 1 1
0 2 3
1 2 3 1 1 4
Sample Output
13
HINT
100%: 1≤N,Q≤200000, 1≤K≤5100%: 1≤N,Q≤200000, 1≤K≤5
题解
看到这题直接就想到了树链剖分+线段树维护
事件0是树剖的常规操作，只要计算出每个点dfs序里的in和out，就可以直接在线段树的相应区间加一个值了
事件1稍微麻烦一些
如果是只有两个节点，那也是常规操作，沿重链上跳到LCA，沿途求和即可
多个节点的话，可以考虑容斥，但那会比较麻烦
我们可以让线段树支持一个覆盖操作，询问时，沿重链上跳到LCA，沿途放标记，表示“需要这一段区间”，询问完成后要在根节点放一个标记，表示“不需要这一段区间”。处理起来有一些细节并不是很好描述，还是看代码吧
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int read()
{
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}
const int N=200010;
struct Edge{int to,next;} e[N<<1];
int h[N],tot=0;
int fa[N],top[N],hson[N],size[N],dep[N];
int in[N],out[N],idex[N],dfn=0;
void add_edge(int u,int v)
{
e[++tot].to=v;
e[tot].next=h[u];
h[u]=tot;
}
void dfs1(int u,int f)
{
size[u]=1;int mx=0;
for(int tmp=h[u];tmp;tmp=e[tmp].next)
{
int v=e[tmp].to;
if(v==f) continue;
dep[v]=dep[u]+1;
fa[v]=u;dfs1(v,u);
size[u]+=size[v];
if(size[v]>mx) mx=size[v],hson[u]=v;
}
}
void dfs2(int u,int tp)
{
top[u]=tp;in[u]=++dfn;idex[dfn]=u;
if(hson[u]) dfs2(hson[u],tp);
for(int tmp=h[u];tmp;tmp=e[tmp].next)
{
int v=e[tmp].to;
if(v==fa[u]||v==hson[u]) continue;
dfs2(v,v);
}
out[u]=dfn;
}
int val[N<<2],sum[N<<2],add[N<<2],mdf[N<<2];
void pushdown(int o,int l,int r)
{
if(add[o])
{
int mid=(l+r)/2;
sum[o*2]+=add[o]*(mid-l+1);
sum[o*2+1]+=add[o]*(r-mid);
add[o*2]+=add[o];
add[o*2+1]+=add[o];
add[o]=0;
}
if(~mdf[o])
{
val[o*2]=sum[o*2]*mdf[o];
val[o*2+1]=sum[o*2+1]*mdf[o];
mdf[o*2]=mdf[o*2+1]=mdf[o];
mdf[o]=-1;
}
}
void maintain(int o)
{
sum[o]=sum[o*2]+sum[o*2+1];
val[o]=val[o*2]+val[o*2+1];
}
void Modify(int o,int l,int r,int nl,int nr,int ty)
{
if(l>=nl&&r<=nr)
{
val[o]=ty*sum[o];
mdf[o]=ty;
return;
}
pushdown(o,l,r);
int mid=(l+r)/2;
if(nl<=mid) Modify(o*2,l,mid,nl,nr,ty);
if(nr>mid) Modify(o*2+1,mid+1,r,nl,nr,ty);
maintain(o);
}
void Add(int o,int l,int r,int nl,int nr,int k)
{
if(l>=nl&&r<=nr)
{
sum[o]+=k*(r-l+1);
add[o]+=k;
return;
}
pushdown(o,l,r);
int mid=(l+r)/2;
if(nl<=mid) Add(o*2,l,mid,nl,nr,k);
if(nr>mid) Add(o*2+1,mid+1,r,nl,nr,k);
maintain(o);
}
void Modify(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
Modify(1,1,dfn,in[top[u]],in[u],1);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
Modify(1,1,dfn,in[u],in[v],1);
}
int main()
{
int n=read(),u,v,opt,k;
for(int i=1;i<n;i++)
{
u=read();v=read();
add_edge(u,v);
add_edge(v,u);
}
dep[1]=1;dfs1(1,0);dfs2(1,1);
int Q=read();
while(Q--)
{
opt=read();
if(opt==0)
{
u=read();k=read();
Add(1,1,n,in[u],out[u],k);
}
else
{
k=read();
for(int i=1;i<=k;i++)
{
u=read();v=read();
Modify(u,v);
}
printf("%d\n",val[1]&INF);
Modify(1,1,n,1,n,0);
}
}
return 0;
}