3786: 星系探索
Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 647 Solved: 212
[Submit][Status][Discuss]
Description
物理学家小C的研究正遇到某个瓶颈。
他正在研究的是一个星系，这个星系中有n个星球，其中有一个主星球(方便起见我们默认其为1号星球)，其余的所有星球均有且仅有一个依赖星球。主星球没有依赖星球。
我们定义依赖关系如下：若星球a的依赖星球是b,则有星球a依赖星球b.此外，依赖关系具有传递性，即若星球a依赖星球b,星球b依赖星球c,则有星球a依赖星球c.
对于这个神秘的星系中，小C初步探究了它的性质，发现星球之间的依赖关系是无环的。并且从星球a出发只能直接到达它的依赖星球b.
每个星球i都有一个能量系数wi.小C想进行若干次实验，第i次实验，他将从飞船上向星球di发射一个初始能量为0的能量收集器，能量收集器会从星球di开始前往主星球，并收集沿途每个星球的部分能量，收集能量的多少等于这个星球的能量系数。
但是星系的构成并不是一成不变的，某些时刻，星系可能由于某些复杂的原因发生变化。
有些时刻，某个星球能量激发，将使得所有依赖于它的星球以及他自己的能量系数均增加一个定值。还有可能在某些时刻，某个星球的依赖星球会发生变化，但变化后依然满足依赖关系是无环的。
现在小C已经测定了时刻0时每个星球的能量系数,以及每个星球(除了主星球之外)的依赖星球。接下来的m个时刻，每个时刻都会发生一些事件。其中小C可能会进行若干次实验，对于他的每一次实验，请你告诉他这一次实验能量收集器的最终能量是多少。
Input
第一行一个整数n,表示星系的星球数。
接下来n-1行每行一个整数,分别表示星球2-n的依赖星球编号。
接下来一行n个整数，表示每个星球在时刻0时的初始能量系数wi.
接下来一行一个整数m,表示事件的总数。
事件分为以下三种类型。
(1)"Q di"表示小C要开始一次实验,收集器的初始位置在星球di.
(2)"C xi yi"表示星球xi的依赖星球变为了星球yi.
(3)"F pi qi"表示星球pi能量激发，常数为qi.
Output
对于每一个事件类型为Q的事件，输出一行一个整数，表示此次实验的收集器最终能量。
Sample Input
1
1
4 5 7
5
Q 2
F 1 3
Q 2
C 2 3
Q 2
Sample Output
15
25
HINT
n<=100000,m<=300000,1<di,xi<=n,wi,qi<=100000.保证操作合法。
Source
Solution
子树有关修改，显然不能用Link-Cut-Tree...
考虑用DFS序，但换根操作显然不能用线段树维护，所以用支持分裂合并的Splay！
我们把DFS序中的入栈出栈分开，在一个点入栈时权值为+val[x]，出栈时权值为-val[x]，这样对于他的子树，影响显然会抵消
这样的话，查询点x到跟的$\sum_{x}^{root}val[x]$，就相当于前缀和查询$\sum_{pl[1]}^{pl[x]}val[x]$
子树修改，就是打标记。
换根操作，把x换到y，先把x的子树区间分裂开，再把y的子树区间提取，然后把x的子树区间连到y的子树区间最左即可
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
inline int read()
{
int x=; char ch=getchar();
while (ch<'' || ch>'') {ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x;
}
#define LL long long
#define MAXN 200010
int N,M,power[MAXN],val[MAXN];
struct EdgeNode{int next,to,d;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
int pl[MAXN],dfn,pr[MAXN],pre[MAXN],del[MAXN];
void DFS(int now,int last)
{
pl[now]=++dfn; pre[dfn]=now; del[dfn]=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last)
DFS(edge[i].to,now);
pr[now]=++dfn; del[dfn]=-;
}
namespace SplayTree
{ int fa[MAXN],son[MAXN][],sz,root,ln[MAXN],rn[MAXN],pos[MAXN];
LL sum[MAXN],tag[MAXN];
//ln记录左的数量，rn记录右的数量，tag标记
#define ls(x) son[x][0]
#define rs(x) son[x][1]
#define INF 1000100 inline void Update(int now)
{
sum[now]=sum[ls(now)]+sum[rs(now)]+(LL)val[now];
ln[now]=ln[ls(now)]+ln[rs(now)]+(del[now]==);
rn[now]=rn[ls(now)]+rn[rs(now)]+(del[now]==-);
}
inline void paint(int now,LL D) {if (now) val[now]+=D*del[now],sum[now]+=D*(ln[now]-rn[now]),tag[now]+=D;}
inline void PushDown(int now)
{
if (!tag[now]) return;
LL D=tag[now]; tag[now]=;
if (ls(now)) paint(ls(now),D);
if (rs(now)) paint(rs(now),D);
}
void print(int now)
{
PushDown(now);
if (val[now]!=INF && val[now]!=-INF)
printf("ID=%d ---%d [%d %d] %d %I64d %d %d %d %I64d\n",
now,fa[now],ls(now),rs(now),val[now],sum[now],ln[now],rn[now],del[now],tag[now]);
if (son[now][]) print(son[now][]);
if (son[now][]) print(son[now][]);
}
inline bool Right(int now) {return son[fa[now]][]==now;}
inline void rotate(int now)
{
PushDown(fa[now]); PushDown(now);
int f=fa[now],gf=fa[f],wh=Right(now);
son[f][wh]=son[now][wh^]; fa[son[f][wh]]=f;
fa[f]=now; son[now][wh^]=f; fa[now]=gf;
if (gf) son[gf][son[gf][]==f]=now;
Update(f); Update(now);
}
inline void splay(int now,int tar)
{
for (int f; (f=fa[now])!=tar; rotate(now))
if (fa[f]!=tar) rotate(Right(now)==Right(f)? f:now);
if (!tar) root=now;
}
inline int fmin(int x) {while (son[x][]) x=son[x][]; return x;}
inline int fmax(int x) {while (son[x][]) x=son[x][]; return x;}
inline void Split(int l,int r)
{
splay(l,); int x=fmax(ls(root));
splay(r,); int y=fmin(rs(root));
splay(x,); splay(y,x);
}
inline LL Query(int pos) {Split(pl[],pl[pos]); return sum[ls(rs(root))];}
inline void Change(int x,int D)
{
Split(pl[x],pr[x]);
int rt=son[rs(root)][];
sum[rt]+=(LL)(ln[rt]-rn[rt])*D; val[rt]+=D*del[rt]; tag[rt]+=D;
Update(rs(root)); Update(root);
}
inline void BuildTree(int l,int r,int last)
{
if (r<l) return;
int mid=(l+r)>>,now=mid;
fa[now]=last; son[last][now>last]=now;
if (l==r)
{sum[now]=val[now]; ln[now]=del[now]==; rn[now]=-ln[now]; return;}
BuildTree(l,mid-,now); BuildTree(mid+,r,now);
Update(now);
}
inline void Init() {BuildTree(,(N<<)+,); root=(+(N<<)+)>>;}
inline void MakeRoot(int now,int father)
{
Split(pl[now],pr[now]);
int rt=ls(rs(root));
fa[ls(rs(root))]=;
son[rs(root)][]=;
Update(rs(root)),Update(root);
splay(pl[father],); splay(fmin(rs(root)),root);
son[rs(root)][]=rt; fa[rt]=rs(root);
Update(rs(root)),Update(root);
}
}
using namespace SplayTree;
int main()
{
N=read();
for (int i=; i<=N; i++) InsertEdge(i,read());
dfn=; DFS(,);
for (int i=; i<=N; i++) power[i]=read();
// for (int i=1; i<=N; i++) printf("id=%d [%d , %d]\n",pre[i],pl[pre[i]],pr[pre[i]]);
for (int i=; i<=N; i++) val[pl[i]]+=power[i],val[pr[i]]-=power[i];
// for (int i=1; i<=dfn; i++) printf("%d ",val[i]); puts("");
M=read();
SplayTree::Init();
while (M--)
{
// print(root);
char opt[]; scanf("%s",opt); int x,y;
if (opt[]=='Q') x=read(),printf("%I64d\n",SplayTree::Query(x));
if (opt[]=='C') x=read(),y=read(),SplayTree::MakeRoot(x,y);
if (opt[]=='F') x=read(),y=read(),SplayTree::Change(x,y);
}
return ;
}
一天前..我：char哥，要是DFS序不用线段树，用Splay的话，不就可以支持子树交换XXX了吗... char哥：...woc！这么科学....
于是跟char哥连坐，写了一天Splay，然后这道题昨天没调出来...
终于写出来了...40s时限41s AC....
我：我一定要压到40s以内！ ..... 我：当我没说；
我：char哥，你有什么压常数的技巧么？ char哥：重写，你这程序已经没救了！......
本机加O2优化：