Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

CF342E Xenia and Tree

Posted on

非常有意思的分块题。

Solution

首先我们先考虑两种不同的暴力：

  • 我们遇到每一个询问时，暴力查找前面每一个修改，遇到修改的复杂度为：$O(1)$，遇到询问的复杂度为：$O(n\log n)$，最低：$O(n)$。

  • 我们遇到每一个修改时，暴力修改剩下的每一个节点距离红色节点的距离，遇到修改的复杂度为：$O(n)$，遇到询问的复杂度为：$O(1)$。

然后我们考虑让它们平衡，首先先对询问分块，对于块内的修改对块内询问的影响，我们暴力$lca$求，然后每块经行完了之后，将这一块内部的所有修改全部压入队列，对树经行一波$bfs$，这样就能解决前面块对后面的影响。

可以做到：$O(n\sqrt n)$或者$O(n\sqrt{n\log n})$。

Code

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
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0;
    bool flag = 0;
    char c = getchar();
    while (c < '0' || '9' < c) { if (c == '-') flag = 1; c = getchar(); }
    while ('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if (flag) res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
    if (res < 0) putchar('-'), res = -res;
    if (res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(const char *s) { while (*s) putchar(*s++); }
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 1e5 + 5;
int n, m;
int limit, len, idx;
int e[N << 1], ne[N << 1], h[N];
inline void add(int x, int y)
{
    idx ++;
    e[idx] = y, ne[idx] = h[x], h[x] = idx;
}
struct Node{
    int op, x;
}q[N];
int maxn[N];
vector<Node>a[N], s;
int depth[N], sz[N], son[N], fa[N], top[N];
void dfs(int x, int y)
{
    depth[x] = depth[y] + 1, sz[x] = 1, fa[x] = y;
    for(int i = h[x], j; ~i;i = ne[i])
    {
        j = e[i];
        if(j == y) continue;
        dfs(j, x);
        sz[x] += sz[j];
        if(sz[j] > sz[son[x]]) son[x] = j;
    }
}
void dfs2(int x, int y)
{
    top[x] = y;
    if(!son[x]) return ;
    dfs2(son[x], y);
    for(int i = h[x], j; ~i;i = ne[i])
    {
        j = e[i];
        if(j == son[x] || j == fa[x]) continue;
        dfs2(j, j);
    }
}
inline int lca(int x, int y)
{
    while(top[x] != top[y])
    {
        if(depth[top[x]] < depth[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if(depth[x] > depth[y]) swap(x, y);
    return x;
}
queue<int> p;
inline void bfs()
{
    while(!p.empty())
    {
        int o = p.front();
        p.pop();
        for(int i = h[o], j; ~i;i = ne[i])
        {
            j = e[i];
            if(maxn[j] > maxn[o] + 1) maxn[j] = maxn[o] + 1, p.push(j);
        }
    }
}
int main()
{
    memset(maxn, 0x3f, sizeof(maxn));
    memset(h, -1, sizeof(h));
    read(n, m);
    for(int i = 1, o, u;i < n;i ++) read(o, u), add(o, u), add(u, o);
    for(int i = 1;i <= m;i ++) read(q[i].op, q[i].x);
    limit = 600;
    for(int i = 1;i <= m;i ++)
    {
        if(limit * len < i) len ++;
        a[len].push_back(q[i]);
    }
    dfs(1, 1);
    dfs2(1, 1);
    maxn[1] = 0;
    p.push(1);
    bfs();
    for(int i = 1;i <= len;i ++)
    {
        for(int j = 0;j < (int)a[i].size();j ++)
        {
            Node x = a[i][j];
            if(x.op == 2)
            {
                int ans = maxn[x.x];
                for(int k = 0;k < j;k ++)
                {
                    Node y = a[i][k];
                    if(y.op == 1)
                    {
                        int z = lca(x.x, y.x);
                        ans = min(ans, depth[x.x] + depth[y.x] - 2 * depth[z]);
                    }
                }
                write(ans, '\n');
            }
        }
        for(Node j : a[i])
            if(j.op == 1) maxn[j.x] = 0, p.push(j.x);
        bfs();
    }
    return 0;
}