NOI 2015パッケージマネージャの問題解&コード

简单的树链断分==但是第一次照片正意义上的树剖坑,我丸5小时了...书いたコードもテンプレートレベルの考え方ではありません.テンプレートはもういくつかの问题を探して习惯を整理しなければなりません.**そうだ==テンプレートを写したことがありません.下のテンプレートは自分で书き方と记忆の难しさによって自分で整理しました.
**二日間調整して、タイトルはもう忘れました.整理して、0をルートノードとするBoolタイプの木を与えました.一つのノードxに対して二つの操作があります.1、そのノードからルートノードへの経路上のすべてのノード値を1に変更します.2、そのノードをルートとするサブツリー上のノードをすべて0に変更します.毎回の操作に対して、今回修正されたノードの数を出力します.
**特に注意が必要なのは、線分ツリーノードのスペースを4倍にすることです…また、dfs番号とノード自体の番号をはっきりさせることです==うん、また、むやみに書くかどうかは考えていません**0番ノードの先頭は結局計算しにくいので、私は番号を全部追加しました.新しい番号の下には、すべてのノードに存在しない父親0ノードがあります

#include<iostream>
#include<vector>
#include<stdio.h>
#define lson (o<<1)
#define rson ((o<<1)|1)
using namespace std;
const int maxn=100005;
int n,q,fa[maxn],x,ans,tot;
int tree[maxn*4],lazy[maxn*4],pa[maxn],son[maxn],rt[maxn],size[maxn];
int in[maxn],out[maxn],deep[maxn];
vector <int> edge[maxn];
char s[10];
int dfs(int r,int d)
{
    deep[r]=d;
    size[r]=1;
    int z=-1;
    for(int i=0;i<edge[r].size();i++)
    {
        size[r]+=dfs(edge[r][i],d+1);
        if(z==-1 || size[edge[r][i]]>size[z])z=edge[r][i];
    }
    son[r]=z;
    return size[r];
}
void buildtree(int c,int root)
{
    in[c]=++tot;
    rt[c]=root;
    if(!edge[c].size())
    {
        out[c]=tot;
        return;
    }
    buildtree(son[c],root);
    for(int i=0;i<edge[c].size();i++)
        if(edge[c][i]!=son[c])
            buildtree(edge[c][i],edge[c][i]);
    out[c]=tot;
}
void pushdown(int o,int l,int r)
{
    if(lazy[o])
    {
        tree[o]=(r-l+1)*(lazy[o]-1);
        if(l!=r)
        {
            int mid=(l+r)/2;
            tree[lson]=(mid-l+1)*(lazy[o]-1);
            tree[rson]=(r-mid)*(lazy[o]-1);
            lazy[lson]=lazy[rson]=lazy[o];
        }
    }
    lazy[o]=0;
}
void maintain(int o,int l,int r)
{
    if(l!=r)tree[o]=tree[lson]+tree[rson];
}
void addtree(int o,int l,int r,int L,int R,int c)
{
    pushdown(o,l,r);
    if(l>R || r<L)return;
    if(l>=L && r<=R)
    {
        lazy[o]=c+1;
        tree[o]=(r-l+1)*(lazy[o]-1);
        return;
    }
    int mid=(l+r)/2;
    addtree(lson,l,mid,L,R,c);
    addtree(rson,mid+1,r,L,R,c);
    maintain(o,l,r);
}
void ins(int o,int c)
{
    bool flag=true;
    ans=tree[1];
    if(c)
    {
        while(o)
        {
            addtree(1,1,tot,in[rt[o]],in[o],c);
            o=fa[rt[o]];
        }
        ans=tree[1]-ans;
    }
    else
    {
        addtree(1,1,tot,in[o],out[o],c);
        ans-=tree[1];
    }
}
int main(void)
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&fa[i]);
        fa[i]++;
        edge[fa[i]].push_back(i);
    }
    dfs(1,1);
    buildtree(1,1);
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%s",s);
        scanf("%d",&x);
        x++;
        ans=0;
        if(s[0]=='u')
        {
            ins(x,0);
            printf("%d
",ans);
        }
        else
        {
            ins(x,1);
            printf("%d
",ans);
        }
    }
    return 0;
}