3589: 动态树
Time Limit: 30 Sec Memory Limit: 1024 MBSubmit: 288 Solved: 109
[Submit][Status][Discuss]
Description
别忘了这是一棵动态树, 每时每刻都是动态的. 小明要求你在这棵树上维护两种事件
事件0:
这棵树长出了一些果子, 即某个子树中的每一个节点都会长出K个果子.
事件1:
小明希望你求出几条树枝上的果子数. 一条树枝事实上就是一个从某个节点到根的路径的一段. 每次小明会选定一些树枝, 让你求出在这些树枝上的节点的果子数的和. 注意, 树枝之间可能会重合, 这时重合的部分的节点的果子仅仅要算一次.
Input
第一行一个整数n(1<=n<=200,000), 即节点数.
接下来n-1行, 每行两个数字u, v. 表示果子u和果子v之间有一条直接的边. 节点从1開始编号.
在接下来一个整数nQ(1<=nQ<=200,000), 表示事件.
最后nQ行, 每行开头要么是0, 要么是1.
假设是0, 表示这个事件是事件0. 这行接下来的2个整数u, delta表示以u为根的子树中的每一个节点长出了delta个果子.
假设是1, 表示这个事件是事件1. 这行接下来一个整数K(1<=K<=5), 表示这次询问涉及K个树枝. 接下来K对整数u_k, v_k, 每一个树枝从节点u_k到节点v_k. 因为果子数可能许多, 请输出这个数模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
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
1 <= n <= 200,000, 1 <= nQ <= 200,000, K = 5.
生成每一个树枝的过程是这种:先在树中随机找一个节点, 然后在这个节点到根的路径上随机选一个节点, 这两个节点就作为树枝的两端.
Source
子树改动和区间并的查询。树链剖分+线段树能够解决。
查询操作仅仅需将链上的点打上标记，终于输出全部标记的点的权值和，注意每次询问后都要去除全部标记。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 200005
using namespace std;
struct edge{int next,to;}e[maxn*2];
struct seg{int l,r,sum,tag[2],ret;}t[maxn*4];
int n,m,x,y,cnt,tot,opt;
int l[maxn],r[maxn],d[maxn];
int fa[maxn],sz[maxn],son[maxn],head[maxn],belong[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add_edge(int x,int y)
{
e[++cnt]=(edge){head[x],y};head[x]=cnt;
e[++cnt]=(edge){head[y],x};head[y]=cnt;
}
inline void dfs1(int x)
{
sz[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if (sz[y]) continue;
d[y]=d[x]+1;
fa[y]=x;
dfs1(y);
sz[x]+=sz[y];
if (sz[y]>sz[son[x]]) son[x]=y;
}
}
inline void dfs2(int x,int chain)
{
l[x]=++tot;belong[x]=chain;
if (son[x]) dfs2(son[x],chain);
for(int i=head[x];i;i=e[i].next)
if (!l[e[i].to]&&e[i].to!=son[x]) dfs2(e[i].to,e[i].to);
r[x]=tot;
}
inline void pushup(int k)
{
t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
t[k].ret=t[k<<1].ret+t[k<<1|1].ret;
}
inline void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;t[k].tag[0]=-1;
if (l==r) return;
int mid=(l+r)>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
inline void update(int k,int z)
{
t[k].tag[1]+=z;
t[k].sum+=z*(t[k].r-t[k].l+1);
}
inline void update2(int k,int z)
{
t[k].tag[0]=z;
t[k].ret=t[k].sum*z;
}
inline void pushdown(int k)
{
if (t[k].tag[1])
{
update(k<<1,t[k].tag[1]);
update(k<<1|1,t[k].tag[1]);
t[k].tag[1]=0;
}
if (t[k].tag[0]!=-1)
{
update2(k<<1,t[k].tag[0]);
update2(k<<1|1,t[k].tag[0]);
t[k].tag[0]=-1;
}
}
inline void change(int k,int x,int y,int z)
{
if (t[k].tag[0]==z) return;
if (t[k].l==x&&t[k].r==y){update2(k,z);return;}
int mid=(t[k].l+t[k].r)>>1;
pushdown(k);
if (y<=mid) change(k<<1,x,y,z);
else if (x>mid) change(k<<1|1,x,y,z);
else{change(k<<1,x,mid,z);change(k<<1|1,mid+1,y,z);}
pushup(k);
}
inline void add(int k,int x,int y,int z)
{
if (t[k].l==x&&t[k].r==y){update(k,z);return;}
int mid=(t[k].l+t[k].r)>>1;
pushdown(k);
if (y<=mid) add(k<<1,x,y,z);
else if (x>mid) add(k<<1|1,x,y,z);
else{add(k<<1,x,mid,z);add(k<<1|1,mid+1,y,z);}
pushup(k);
}
inline void solve(int x,int y,int z)
{
while (belong[x]!=belong[y])
{
if (d[belong[x]]<d[belong[y]]) swap(x,y);
change(1,l[belong[x]],l[x],z);
x=fa[belong[x]];
}
if (d[x]>d[y]) swap(x,y);
change(1,l[x],l[y],z);
}
int main()
{
n=read();
F(i,1,n-1) add_edge(read(),read());
d[1]=1;dfs1(1);dfs2(1,1);
build(1,1,n);
m=read();
while(m--)
{
opt=read();x=read();
if (opt)
{
F(i,1,x) solve(read(),read(),1);
printf("%d
",t[1].ret&((1<<31)-1));
update2(1,0);
}
else add(1,l[x],r[x],read());
}
}