洛谷 P2146 [NOI2015]软件包管理器

题目：软件包管理器

思路：树剖模板题。

代码：

#include<bits/stdc++.h>
using namespace std;#define maxn 100000
#define read(x) scanf("%d",&x)int n;struct Node{
    int lstid;int fa,hson;int sz,d,tp;
};Node a[maxn+5];
vector<int> tr[maxn+5];int cnt=0,pre[maxn+5];struct segTree {
    #define lson (o*2)#define rson (o*2+1)#define mid (L+(R-L)/2)int c[maxn*10+5],lzy[maxn*10+5];int len[maxn*10+5];void push_up(int o) {
    c[o]=c[lson]+c[rson];}void build(int o,int L,int R) {
    len[o]=R-L+1,lzy[o]=-1;if(L==R) return ;build(lson,L,mid),build(rson,mid+1,R);}int P,Q;void push_down(int o) {
    if(lzy[o]==-1) return ;lzy[lson]=lzy[o],lzy[rson]=lzy[o];c[lson]=lzy[o]*len[lson],c[rson]=lzy[o]*len[rson];lzy[o]=-1;}int Qry(int o,int L,int R) {
    if(L>Q||R<P) return 0;if(L>=P&&R<=Q) return c[o];push_down(o);int ans=Qry(lson,L,mid)+Qry(rson,mid+1,R);return ans;}int Query(int x,int y) {
    if(x>y) swap(x,y);P=x,Q=y;return Qry(1,1,n);}void Upd(int o,int L,int R,int d) {
    if(L>Q||R<P) return ;if(L>=P&&R<=Q) {
    c[o]=d*len[o];lzy[o]=d;return ;}push_down(o);Upd(lson,L,mid,d),Upd(rson,mid+1,R,d);push_up(o);}void Update(int x,int y,int d) {
    if(x>y) swap(x,y);P=x,Q=y;Upd(1,1,n,d);}
};segTree sgtr;struct HLD{
    int Query(int x,int y) {
    int ans=0;while(a[x].tp!=a[y].tp) {
    if(a[a[x].tp].d<a[a[y].tp].d) swap(x,y);ans+=sgtr.Query(a[a[x].tp].lstid,a[x].lstid);x=a[a[x].tp].fa;}ans+=sgtr.Query(a[x].lstid,a[y].lstid);return ans;}void Update(int x,int y,int z) {
    while(a[x].tp!=a[y].tp) {
    if(a[a[x].tp].d<a[a[y].tp].d) swap(x,y);sgtr.Update(a[a[x].tp].lstid,a[x].lstid,z);x=a[a[x].tp].fa;}sgtr.Update(a[x].lstid,a[y].lstid,z);}
};HLD hld;void readin() {
    read(n);for(int i=2;i<=n;i++) read(a[i].fa),tr[++a[i].fa].push_back(i);
}void dfs1(int x) {
    a[x].sz=1,a[x].d=a[a[x].fa].d+1;for(int i=0;i<tr[x].size();i++) {
    int y=tr[x][i];dfs1(y);a[x].sz+=a[y].sz;if(a[y].sz>a[a[x].hson].sz) a[x].hson=y;}
}void dfs2(int x,int tp) {
    pre[++cnt]=x,a[x].lstid=cnt;a[x].tp=tp;if(!a[x].hson) return ;else dfs2(a[x].hson,tp);for(int i=0;i<tr[x].size();i++) {
    int y=tr[x][i];if(y==a[x].hson) continue;dfs2(y,y);}
}int main() {
    readin();dfs1(1);dfs2(1,1);sgtr.build(1,1,n);int T;read(T);while(T--) {
    char opr[20];int x;scanf("%s",opr);read(x),x++;if(opr[0]=='i') {
    printf("%d\n",a[x].d-hld.Query(1,x));hld.Update(1,x,1);} else {
    printf("%d\n",sgtr.Query(a[x].lstid,a[x].lstid+a[x].sz-1));sgtr.Update(a[x].lstid,a[x].lstid+a[x].sz-1,0);}}return 0;
}