Dylan's Blog
0%

Posted on Edited on In

问题描述

你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m≥2)个软件包A1,A2,A3,…,Am，其中A1依赖A2，A2依赖A3，A3依赖A4，……，Am−1依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。

输入

第1行包含1个整数n，表示软件包的总数。软件包从0开始编号。随后一行包含n−1个整数，相邻整数之间用单个空格隔开，分别表示1,2,3,⋯,n−2,n−1号软件包依赖的软件包的编号。

接下来一行包含1个整数q，表示询问的总数。之后q行，每行1个询问。询问分为两种： install x：表示安装软件包x uninstall x：表示卸载软件包x 你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。

对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）

输出

输出文件包括q行。

输出文件的第i行输出1个整数，为第i步操作中改变安装状态的软件包数。

数据范围

对于全部数据：n<=100000, q<=100000。

思路

我们可以看出这些软件的依赖关系是一棵树。设未安装的节点权值为0，安装的权值为1。

然后install操作就是让x节点到根节点路径上权值为0的节点变为1，并输出权值为0节点个数。uninstall操作就是让x子树权值为1的节点变为0，并输出权值为1节点个数。

然后这就是一个很裸的树剖啦QVQ 线段树上的操作就是将整个区间变为0或1。

但是要注意常数问题！以install操作为例，如果先计算x到根节点权值之和，然后进行修改，再求一遍到根节点之和。这样的常数巨大，在BZOJ上会TLE。QWQ

所以我们可以优化一下,先保存一下整棵树权值之和(就是sum[1])，然后修改，输出整棵树前后权值之差。这样常数就小了不少。

细节

  1. 所有点的编号都要+1，不然树剖时会产生与0号节点有关的bug。
  2. lazytag要注意，初始赋为-1，下传标记时新tag要覆盖掉原tag。
  3. 要注意常数，TLE了一次QWQ

代码

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
#include <bits/stdc++.h>
#define MAXN 100005
#define INF 1e9
#define ls (l+r<<1)
#define rs (l+r<<1|1)
#define mid (l+r>>1)
using namespace std;

int n, x, q, cnt, head[MAXN], tag[MAXN*4], sum[MAXN*4];
int Index, son[MAXN], f[MAXN], dep[MAXN], size[MAXN], id[MAXN], top[MAXN];
char opt[100];
struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs1(int x, int fa, int deep)
{
    dep[x]=deep; f[x]=fa; size[x]=1;
    int maxson=-1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs1(to, x, deep+1);
        size[x]+=size[to];
        if(size[to]>maxson) maxson=size[to], son[x]=to;
    }
}

void dfs2(int x, int topf)
{
    id[x]= ++Index; top[x]=topf;
    if(!son[x]) return;
    dfs2(son[x], topf);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==son[x] || to==f[x]) continue;
        dfs2(to, to);
    }
}

void down(int root, int l, int r)
{
    if(tag[root]==-1) return;
    sum[ls]=(mid-l+1)*tag[root];
    sum[rs]=(r-mid)*tag[root];
    tag[ls]=tag[root];
    tag[rs]=tag[root];
    tag[root]=-1;
}

void update(int root, int l, int r, int x, int y, int z)
{
    if(x>r || y<l) return ;
    if(x<=l && y>=r)
    {
        sum[root]=(r-l+1)*z;
        tag[root]=z;
        return;
    }
    down(root, l, r);
    update(ls, l, mid, x, y, z);
    update(rs, mid+1, r, x, y, z);
    sum[root]=sum[ls]+sum[rs];
}

void act(int x, int y)
{
    while(top[x]!=1)
    {
        update(1, 1, n, id[top[x]], id[x], y);
        x=f[top[x]];
    }
    update(1, 1, n, id[1], id[x], y);
}

int main()
{
    memset(tag, -1, sizeof(-1));
    scanf("%d", &n);
    for(int i=2; i<=n; i++)
    {
        scanf("%d", &x);
        addedge(i, x+1); 
        addedge(x+1, i);
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    scanf("%d", &q);
    for(int i=1; i<=q; i++)
    {
        scanf("%s%d", opt, &x); x++;
        int temp=sum[1];
        if(opt[0]=='i')
        {
            act(x, 1);
            printf("%dn", sum[1]-temp);
        }
        if(opt[0]=='u')
        {
            update(1, 1, n, id[x], id[x]+size[x]-1, 0);
            printf("%dn", temp-sum[1]);
        }
    }
}