傳送門(mén):?？?/p>

題目描述:

華華看書(shū)了解到，一起玩養(yǎng)成類(lèi)的游戲有助于兩人培養(yǎng)感情。所以他決定和月月一起種一棵樹(shù)。因?yàn)槿A華現(xiàn)在也是信息學(xué)高手了，所以他們種的樹(shù)是信息學(xué)意義下的。
華華和月月一起維護(hù)了一棵動(dòng)態(tài)有根樹(shù)，每個(gè)點(diǎn)有一個(gè)權(quán)值。剛開(kāi)存檔的時(shí)候，樹(shù)上只有 0 號(hào)節(jié)點(diǎn)，權(quán)值為 0 。接下來(lái)有兩種操作：
操作 1：輸入格式1 i，表示月月氪金使節(jié)點(diǎn) i 長(zhǎng)出了一個(gè)新的兒子節(jié)點(diǎn)，權(quán)值為0，編號(hào)為當(dāng)前最大編號(hào) +1（也可以理解為，當(dāng)前是第幾個(gè)操作 1，新節(jié)點(diǎn)的編號(hào)就是多少）。
操作 2：輸入格式2 i a，表示華華上線做任務(wù)使節(jié)點(diǎn) i 的子樹(shù)中所有節(jié)點(diǎn)（即它和它的所有子孫節(jié)點(diǎn)）權(quán)值加 a 。
但是月月有時(shí)會(huì)檢查華華有沒(méi)有認(rèn)真維護(hù)這棵樹(shù)，會(huì)作出詢(xún)問(wèn)：
詢(xún)問(wèn) 3：輸入格式3 i，華華需要給出 i 節(jié)點(diǎn)此時(shí)的權(quán)值。
華華當(dāng)然有認(rèn)真種樹(shù)了，不過(guò)還是希望能寫(xiě)個(gè)程序以備不時(shí)之需。
輸入:
9
1 0
2 0 1
3 0
3 1
1 0
1 1
2 0 2
3 1
3 3
輸出:
1
1
3
2

樹(shù)上操作,使用樹(shù)鏈剖分+線段樹(shù)進(jìn)行解決

對(duì)于操作2和操作3,我們可以將樹(shù)形結(jié)構(gòu)分解成線性結(jié)構(gòu)然后使用線段樹(shù)進(jìn)行維護(hù)區(qū)間修改即可.對(duì)于分解樹(shù)形結(jié)構(gòu)的算法可以使用dfs序進(jìn)行解決,也可以使用樹(shù)鏈剖分進(jìn)行解決.兩者相比,dfs序的代碼量更短,但是樹(shù)鏈剖分能解決的情況更為普遍,所以對(duì)于本題來(lái)說(shuō),博主使用的樹(shù)鏈剖分算法

對(duì)于操作一,我們發(fā)現(xiàn)我們需要?jiǎng)討B(tài)的對(duì)樹(shù)進(jìn)行加點(diǎn)操作,對(duì)于這種操作,我們發(fā)現(xiàn)很難進(jìn)行維護(hù).所以我們考慮進(jìn)行離線維護(hù).對(duì)于所有的加點(diǎn)操作,我們都假設(shè)全部都已經(jīng)完成.建一顆最終的樹(shù).然后對(duì)于這些樹(shù)來(lái)說(shuō),我們對(duì)此每一個(gè)節(jié)點(diǎn)使用操作2.

此時(shí)肯定會(huì)發(fā)現(xiàn)這種做法存在這樣的一個(gè)問(wèn)題,因?yàn)槲覀兇藭r(shí)對(duì)$u$的所有節(jié)點(diǎn)增加了一個(gè)權(quán)值,但是對(duì)于$u$的一些節(jié)點(diǎn)(假設(shè)為v)來(lái)說(shuō),可以本來(lái)是在這個(gè)操作之后才產(chǎn)生的,所以此時(shí)我們的操作是錯(cuò)誤的.所幸的是此時(shí)我們需要統(tǒng)計(jì)的只是單點(diǎn)的全職,所以此時(shí)當(dāng)我們v還未出現(xiàn)之前,我們直接將v的權(quán)值改變了對(duì)于我們的查詢(xún)來(lái)說(shuō)并沒(méi)有問(wèn)題,因?yàn)槲覀兇藭r(shí)根本不會(huì)查詢(xún)這個(gè)點(diǎn).然后當(dāng)我們的這個(gè)點(diǎn)出現(xiàn)之后,只要將這個(gè)點(diǎn)的權(quán)值歸0即可,此時(shí)我們的v節(jié)點(diǎn)就可以保證正確性了

為了操作方便,可以將所有節(jié)點(diǎn)的編號(hào)加一

下面是具體的代碼部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int fa[maxn],dep[maxn],max_son[maxn],Size[maxn];
vector<int>edge[maxn];
void dfs1(int u,int pre_u) {Size[u]=1;for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==pre_u) continue;dep[v]=dep[u]+1;dfs1(v,u);fa[v]=u;Size[u]+=Size[v];if(Size[v]>Size[max_son[u]]) {max_son[u]=v;}}
}
int top[maxn],id[maxn],rev[maxn],tot=0;
void dfs2(int u,int t) {top[u]=t;id[u]=++tot;rev[tot]=u;if(!max_son[u]) return ;dfs2(max_son[u],t);for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==fa[u]||v==max_son[u]) continue;dfs2(v,v);}
}
struct Segment_tree{int l,r,sum,lazy;
}tree[maxn*4];int w[maxn];
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;tree[rt].sum=tree[rt].lazy=0;if(l==r) return ;int mid=(l+r)>>1;build(lson);build(rson);
}
void pushup(int rt) {tree[rt].sum=tree[ls].sum+tree[rs].sum;
}
void change(int rt,int val) {int len=tree[rt].r-tree[rt].l+1;tree[rt].sum+=len*val;tree[rt].lazy+=val;
}
void pushdown(int rt) {change(ls,tree[rt].lazy);change(rs,tree[rt].lazy);tree[rt].lazy=0;
}
void update(int l,int r,int rt,int val) {if(tree[rt].l==l&&tree[rt].r==r) {change(rt,val);return ;}if(tree[rt].lazy) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) update(l,r,ls,val);else if(l>mid) update(l,r,rs,val);else update(l,mid,ls,val),update(mid+1,r,rs,val);pushup(rt);
}
int query(int pos,int rt) {if(tree[rt].l==pos&&tree[rt].r==pos) {return tree[rt].sum;}if(tree[rt].lazy) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(pos<=mid) return query(pos,ls);else return query(pos,rs);
}
struct OPT{int opt,pos,Date;
}opt[maxn];
int main() {int m=read();int cnt=1;for(int i=1;i<=m;i++) {opt[i].opt=read(); if(opt[i].opt==1) {opt[i].pos=read();edge[opt[i].pos+1].push_back(++cnt);opt[i].Date=cnt;}else if(opt[i].opt==2) {opt[i].pos=read();opt[i].Date=read();}else {opt[i].pos=read();}}dfs1(1,0);dfs2(1,1);build(1,tot,1);for(int i=1;i<=m;i++) {if(opt[i].opt==1) {int u=opt[i].Date;int t=query(id[u],1);update(id[u],id[u],1,-t);}else if(opt[i].opt==2) {int u=opt[i].pos+1;update(id[u],id[u]+Size[u]-1,1,opt[i].Date);}else {int u=opt[i].pos+1;printf("%d\n",query(id[u],1));}}return 0;
}