P2146 [NOI2015]软件包管理器(树链剖分+线段树区间覆盖）

题目链接
题目大意（简化）：给你一棵树，编号从0到n-1，给你两种操作：

1. in u 查找从u结点到根节点的路径上有多少个0，并将他们置为1，输出。
2. un u 查找以u为根的子树有多少个1，输出并将他们置为0.

大体思路：很明显，查找以u为根的子树可以用dfs序直接修改，但是查找从u到根节点的路径上的信息暴力的话是O（n）很明显不可以，所以考虑到树链剖分。然后线段树维护区间信息。
注意点：除去线段树的基本操作，只有一个需要注意的地方，就是编号是从0开始，如果结点编号不加1的话就要把son[]数组初始值置为-1，否则就会无限跳，造成超时。（血的教训）

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#define lk (k<<1)
#define rk (k<<1|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pi=acos(-1.0);
const double eps=1e-8;
const double INF=1e20;
const int inf=0x3f3f3f3f;
const int N=1e5+10;
struct egde
{
    int v,next;
}e[N<<1];
int head[N],cnt;
void add(int u,int v)
{
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
int top[N],dfn[N],len,out[N];
int fa[N],dep[N],son[N],size[N];
void dfs1(int u,int f)
{
    fa[u]=f;
    dep[u]=dep[f]+1;
    size[u]=1;
    son[u]=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==f) continue;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[v]>size[son[u]]) son[u]=v;
    }
}
void dfs2(int u)
{
    dfn[u]=++len;
    if(son[u])
    {
        top[son[u]]=top[u];
        dfs2(son[u]);
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(!top[v])
        {
            top[v]=v;
            dfs2(v);
        }
    }
    out[u]=len;
}
struct node
{
    int l,r;
    int sum,lazy;
}t[N<<2];
inline void pushup(int k)
{
    t[k].sum=t[lk].sum+t[rk].sum;
}
inline void pushdown(int k)
{
    if(t[k].lazy!=-1)
    {
        t[lk].lazy=t[rk].lazy=t[k].lazy;
        t[lk].sum=(t[lk].r-t[lk].l+1)*t[k].lazy;
        t[rk].sum=(t[rk].r-t[rk].l+1)*t[k].lazy;
        t[k].lazy=-1;
    }
}
void build(int k,int l,int r)
{
    t[k].l=l;
    t[k].r=r;
    t[k].lazy=-1;
    t[k].sum=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lk,l,mid);
    build(rk,mid+1,r);
}
int x;
void update(int k,int l,int r,int val)
{
    if(t[k].l>=l&&t[k].r<=r)
    {
        x+=t[k].sum;
        t[k].sum=(t[k].r-t[k].l+1)*val;
        t[k].lazy=val;
        return;
    }
    else
    {
        pushdown(k);
        int mid=(t[k].l+t[k].r)>>1;
        if(l<=mid) update(lk,l,r,val);
        if(r>mid) update(rk,l,r,val);
        pushup(k);
    }
}
int ask(int u,int v)
{
    int fu=top[u],fv=top[v];
    int ans=0;
    while(fu!=fv)
    {
        x=0;
        if(dep[fu]>=dep[fv])
        {
            update(1,dfn[fu],dfn[u],1);
            ans+=x;
            u=fa[fu];fu=top[u];
        }
        else {
            update(1,dfn[fv],dfn[v],1);
            ans+=x;
            v=fa[fv];fv=top[v];
        }
    }
    x=0;
    if(dep[u]>=dep[v]) update(1,dfn[v],dfn[u],1),ans+=x;
    else update(1,dfn[u],dfn[v],1),ans+=x;
    return ans;
}
int read()
{
    char c;
    int res=0,sign=1;
    c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') sign=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        res=res*10+c-'0';
        c=getchar();
    }
    return sign*res;
}
void print(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,val,q,u,ans;
char s[10];
int main()
{
    cnt=len=0;
    n=read();
    for(int i=2;i<=n;i++)
    {
        val=read();
        val++;
        add(val,i);
        top[i]=0;
    }
    dfs1(1,0);
    top[1]=1;
    dfs2(1);
    build(1,1,len);
    q=read();
    while(q--)
    {
        scanf("%s",s);
        u=read();
        u++;
        x=0;
        if(s[0]=='i')
        {
            ans=ask(u,1);
            print(dep[u]-dep[1]+1-ans);
            putchar('\n');
        }
        else
        {
            update(1,dfn[u],out[u],0);
            print(x);
            putchar('\n');
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196