2020牛客暑期多校训练营（第九场）D.Groundhog and Golden Apple

发表于 | 阅读数

给定一颗树，每条边$[L_i,R_i]$的人可以通过。每个人可以额外走$0/1$条不符合要求的边，询问每个人可以到达点的数量之和。

显然是线段树分治。但是维护并茶几毕竟麻烦。

  • $k=0$ ,显然即是自己的联通块大小。
  • $k=1$ ,显然即是自己的联通块大小$+$连接出去的联通块大小，显然不可能重新遍历一遍。 考虑这题用的是树，那么一个联通快一定有最高点和最低点。$ans=$ 自己联通块大小$+$最高点父亲联通快大小$+$ 最低点的儿子联通块大小。
  • 维护最高点父亲，每次合并时合并最高点即可。
  • 维护最低点的儿子联通块大小，初始化的时候就是儿子的数量，当维护最高点父亲，此时相对与最高点父亲所在联通快的最低点的儿子联通块大小，也变大了。
  • 合并$x$,$y$时假设拥有最高点的联通块在$x$，那么此时的合并使得最低点的儿子联通块大小增加了$son_{sum}[find(y)]-siz[find(y)]$
代码 
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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
int dep[N];
int ft[N];
int son[N];
struct Dsu
{
    int fa[N], d[N], sum[N], top[N];
    struct Tmp
    {
        int x, y, add, siz, top;
        int sy;
        int tt, st;
    };
    stack<Tmp> s;
    int find(int x)
    {
        while (x != fa[x])
            x = fa[x];
        return x;
    }
    void init(int n)
    {
        while (!s.empty())
            s.pop();
        for (int i = 1; i <= n; i++)
            fa[i] = i, d[i] = 0, sum[i] = 1, top[i] = i;
    }
    void merge(int x, int y)
    {
        int xx = find(x);
        int yy = find(y);
        if (xx == yy)
            return;
        if (d[xx] > d[yy])
            swap(xx, yy);

        if (dep[top[xx]] < dep[top[yy]])
        {

            int tt = find(ft[top[xx]]);

            s.push((Tmp){xx, yy, d[yy], sum[yy], top[yy], son[yy], tt, son[tt]});
            top[yy] = top[xx];
            son[yy] += son[xx] - sum[yy];
            son[tt] += sum[yy];
        }
        else
        {

            int tt = find(ft[top[yy]]);
            s.push((Tmp){xx, yy, d[yy], sum[yy], top[yy], son[yy], tt, son[tt]});
            son[yy] += son[xx] - sum[xx];
            son[tt] += sum[xx];
        }

        fa[xx] = yy;
        sum[yy] += sum[xx];
        d[yy] += (d[xx] == d[yy]);
    }
    void ret(int o)
    {
        while (s.size() > o)
        {
            Tmp x = s.top();
            fa[x.x] = x.x;
            d[x.y] = x.add;
            sum[x.y] = x.siz;
            top[x.y] = x.top;
            son[x.y] = x.sy;
            son[x.tt] = x.st;
            s.pop();
        }
    }
} t;
vector<pii> g[N];
vector<pii> e[N];
int ans[N], k[N];
void insert(int pos, int ql, int qr, int l, int r, pii o)
{
    if (ql <= l && r <= qr)
    {
        e[pos].push_back(o);
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid)
        insert(pos << 1, ql, qr, l, mid, o);
    if (qr > mid)
        insert(pos << 1 | 1, ql, qr, mid + 1, r, o);
}
int ls[N], rs[N];
void solve(int pos, int l, int r)
{
    int o = t.s.size();
    for (pii now : e[pos])
    {
        //cout << l << " " << r << " " << now.first << " " << now.second << endl;

        t.merge(now.first, now.second);
    }
    if (l == r)
    {

        int x = t.find(l), y = t.find(ft[t.top[x]]);

        ans[l] = t.sum[x] + (k[l] == 1 ? (t.sum[y] + son[x]) : 0);
    }
    else
    {
        int mid = (l + r) >> 1;
        solve(pos << 1, l, mid), solve(pos << 1 | 1, mid + 1, r);
    }
    t.ret(o);
}
void dfs(int x, int f)
{
    dep[x] = dep[f] + 1;
    for (pii now : g[x])
    {
        int to = now.first;
        if (to == f)
            continue;
        son[x]++;
        ft[to] = x;
        dfs(to, x);
    }
}
int main()
{
    int n = read();
    for (int i = 1; i <= n; i++)
        k[i] = read();
    t.init(n);
    for (int i = 1; i < n; i++)
    {
        int u = read(), v = read();
        ls[i] = read(), rs[i] = read();
        g[u].push_back(mk(v, i));
        g[v].push_back(mk(u, i));
        insert(1, ls[i], rs[i], 1, n, mk(u, v));
    }
    dfs(1, 0);
    solve(1, 1, n);
    for (int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
}