3589: 动态树
Time Limit: 30 Sec Memory Limit: 1024 MB
Submit: 405 Solved: 137
[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
Solution
真丶动态树，直接用树链剖分水过
首先树链剖分不解释，子树修改？水过
在于查询多段路径的并。
一开始想的是这不直接覆盖么...然后水水的一波..打完发现哦,这是树,不能这么搞...
难道真的要写LCT?其实不用...
思考可以在路径上的点打标记,沿着有标记的路径求和?似乎可以,但没实现
对于路径的求并,可以考虑容斥原理,应该很优,但是不会TAT
所以是某奇怪的姿势:
线段覆盖!详见CodeVS线段覆盖..
很显然,对于树链剖分,是把树上的点映射到序列上,那么对于路径的询问其实就是路径上的多段区间的询问
多次询问就是多次多段区间的询问,考虑直接把这些区间拿出来,然后利用线段覆盖的姿势合并这些区间,对合并后的统计答案即可
这里结果会很大,所以可以让结果自然溢出,最后结果&MaxInt可以变回正数,int的自然溢出是在$-2^{31}-0$循环,unsignedint的是在$-2^{32}-0$循环
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define maxn 210000
int n,q;
struct Edgenode{int to,next;}edge[maxn<<];
int head[maxn],cnt=;
void add(int u,int v){cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt;}
void insert(int u,int v){add(u,v); add(v,u);}
//
//int fa[maxn],son[maxn],deep[maxn],size[maxn],pl[maxn],sz,pr[maxn],pre[maxn],top[maxn];
int fa[maxn],top[maxn],son[maxn];
int size[maxn],pl[maxn],pr[maxn],sz,pre[maxn],deep[maxn];
void dfs_1(int now)
{
size[now]=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=fa[now])
{
fa[edge[i].to]=now;
deep[edge[i].to]=deep[now]+;
dfs_1(edge[i].to);
if (size[son[now]]<size[edge[i].to]) son[now]=edge[i].to;
size[now]+=size[edge[i].to];
}
}
void dfs_2(int now,int chain)
{
pl[now]=++sz;pre[sz]=now;top[now]=chain;
if (son[now]) dfs_2(son[now],chain);
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=son[now] && edge[i].to!=fa[now])
dfs_2(edge[i].to,edge[i].to);
pr[now]=sz;
}
//
struct Treenode{int l,r,size,sum,tag;}tree[maxn<<];
void update(int now)
{
tree[now].sum=tree[now<<].sum+tree[now<<|].sum;
}
void pushdown(int now)
{
if (tree[now].tag)
{
tree[now<<].tag+=tree[now].tag;tree[now<<|].tag+=tree[now].tag;
tree[now<<].sum+=tree[now].tag*tree[now<<].size;
tree[now<<|].sum+=tree[now].tag*tree[now<<|].size;
tree[now].tag=;
}
}
void build(int now,int l,int r)
{
tree[now].l=l; tree[now].r=r; tree[now].size=r-l+;
tree[now].tag=; tree[now].sum=;
if (l==r) return;
int mid=(l+r)>>;
build(now<<,l,mid); build(now<<|,mid+,r);
update(now);
}
void change(int now,int L,int R,int D)
{
pushdown(now);
if (L<=tree[now].l && R>=tree[now].r)
{tree[now].sum+=D*tree[now].size; tree[now].tag+=D; return;}
int mid=(tree[now].l+tree[now].r)>>;
if (L<=mid) change(now<<,L,R,D);
if (mid<R) change(now<<|,L,R,D);
update(now);
}
int query(int now,int L,int R)
{
pushdown(now);
if (L<=tree[now].l && R>=tree[now].r) return tree[now].sum;
int mid=(tree[now].l+tree[now].r)>>,ans=;
if (L<=mid) ans+=query(now<<,L,R);
if (mid<R) ans+=query(now<<|,L,R);
// printf("%d\n",ans); puts("OK");
return ans;
}
//
struct Linenode
{
int u,v;
bool operator < (const Linenode & A) const
{return u<A.u;}
}line[maxn]; int ln;
void AddLine(int x,int y)
{
ln++;line[ln].u=x;line[ln].v=y;
}
void GetLine(int x,int y)
{
while (top[x]!=top[y])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
AddLine(pl[top[x]],pl[x]);
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
AddLine(pl[x],pl[y]);
}
void Ask()
{
sort(line+,line+ln+);
int L=line[].u,R=line[].v,ans=;
for (int i=; i<=ln; i++)
if (line[i].u>R) ans+=query(,L,R),L=line[i].u,R=line[i].v;
else R=max(R,line[i].v);
ans+=query(,L,R);
printf("%d\n",ans&);
}
//
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
n=read();
for (int u,v,i=; i<=n-; i++) u=read(),v=read(),insert(u,v);
dfs_1(); dfs_2(,); build(,,sz);
// for (int i=1; i<=n; i++) printf("%d %d %d %d %d\n",i,pl[i],pr[i],top[i],son[i]);
q=read();
for (int i=; i<=q; i++)
{
int opt=read(),a,b,k;
if (opt==) {a=read(),b=read(),change(,pl[a],pr[a],b);continue;}
ln=; k=read();
for (int j=; j<=k; j++)
a=read(),b=read(),GetLine(a,b);
Ask();
}
return ;
}
一个智障的Interesting的故事:调了2h+的题,一直WA,后来发现提交时一直忘关文件,于是妥A了.....Let's ORZ YveH
