傳送門:牛客

題目描述:

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

樹上操作,使用樹鏈剖分+線段樹進行解決

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

對于操作一,我們發(fā)現(xiàn)我們需要動態(tài)的對樹進行加點操作,對于這種操作,我們發(fā)現(xiàn)很難進行維護.所以我們考慮進行離線維護.對于所有的加點操作,我們都假設全部都已經(jīng)完成.建一顆最終的樹.然后對于這些樹來說,我們對此每一個節(jié)點使用操作2.

此時肯定會發(fā)現(xiàn)這種做法存在這樣的一個問題,因為我們此時對$u$的所有節(jié)點增加了一個權值,但是對于$u$的一些節(jié)點(假設為v)來說,可以本來是在這個操作之后才產(chǎn)生的,所以此時我們的操作是錯誤的.所幸的是此時我們需要統(tǒng)計的只是單點的全職,所以此時當我們v還未出現(xiàn)之前,我們直接將v的權值改變了對于我們的查詢來說并沒有問題,因為我們此時根本不會查詢這個點.然后當我們的這個點出現(xiàn)之后,只要將這個點的權值歸0即可,此時我們的v節(jié)點就可以保證正確性了

為了操作方便,可以將所有節(jié)點的編號加一

下面是具體的代碼部分:

#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;
}