(sp10707)Count on a tree II

发表于

原题链接

思路：

该题是树上莫队的模板。除去和树有关的部分，“不同颜色数” 也是很常见的莫队题型。

和树链相关的问题可以使用欧拉序解决。

欧拉序是一种特殊的 dfs 序，每个点在序列中会被记录两次：进入该节点时和访问完该节点的子树时。

使用欧拉序后就可以将树链的询问变为区间的询问：每个不在指定树链上的点要么不出现，要么出现两次，可以通过这一点来去掉这些点的贡献。

一个特例是当 \(lca(x,y) \neq x \lor y\) 时的 \(lca(x,y)\)，由于 x,y 均在其 lca 的子树中，所以 \(lca(x,y)\) 不会出现在 x,y 的欧拉序区间中，此时需要额外加上 lca 的贡献。

同时注意欧拉序长度为 2n，块长需要设置为 \(\sqrt{2n}\)。

代码：

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
#include <iostream>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Mn(100050),Mm(100500);

template<typename T>
void qrd(T& x) {    //快读
    x = 0;
    char c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c-'0';
        c = getchar();
    }
}

int n,m;
int a[Mn],dca[Mn],pa[Mn];   //原数组，离散化，离散化后位置

struct edge{    //链式前向星
    int e,nt;
}ed[Mn*2];
int vs[Mn];
void adde(int u,int v) {
    static int ec(0);
    ed[++ec] = {v,vs[u]};
    vs[u] = ec;
}
/* 使用树剖求lca，同时生成欧拉序 */
int ts(0);  //时间戳
int tl[Mn*2],tin[Mn],tout[Mn];  //欧拉序，进入时间，离开时间
int fa[Mn], dep[Mn], sz[Mn], hsn[Mn];
//父节点，深度，子树大小，重儿子
void dfs(int x) {   //求重儿子
    sz[x] = 1;
    for(int i(vs[x]);i;i=ed[i].nt) {
        edge& e(ed[i]);
        if(!sz[e.e]) {
            fa[e.e] = x;
            dep[e.e] = dep[x]+1;
            dfs(e.e);
            sz[x] += sz[e.e];
            if(sz[e.e] > sz[hsn[x]]) {
                hsn[x] = e.e;
            }
        }
    }
}
int lt[Mn]; //树剖链顶
void dfs2(int x) {  //树剖+欧拉序
    /* 进入 */
    tin[x] = ++ts;
    tl[ts] = x;
    if(hsn[x]) {
        lt[hsn[x]] = lt[x];
        dfs2(hsn[x]);
    }
    for(int i(vs[x]);i;i=ed[i].nt) {
        edge& e(ed[i]);
        if(fa[e.e]==x && e.e!=hsn[x]) {
            lt[e.e] = e.e;
            dfs2(e.e);
        }
    }
    tout[x] = ++ts;
    tl[ts] = x;
    /* 离开 */
}
int lca(int x,int y) {  //树剖lca
    while(lt[x]!=lt[y]) {
        if(dep[lt[x]]<dep[lt[y]]) {
            x ^= y ^= x ^= y;
        }
        x = fa[lt[x]];
    }
    if(dep[x]<dep[y]) {
        x ^= y ^= x ^= y;
    }
    return y;
}

int bl; //块长
int b[Mn];  //块编号
struct qry {
    int l,r,lx,i;   //lx为lca
    bool operator < (const qry& rhs) const {
        if(b[l]==b[rhs.l]) {
            if(b[l]&1) {
                return r<rhs.r;
            } else {
                return r>rhs.r;
            }
        } else {
            return b[l]<b[rhs.l];
        }
    }
}aq[Mm];
bool isi[Mn];   //是否只询问一次
int cnt[Mn],ans[Mn],tmp(0);
//计数，答案，临时答案
void change(int p) {    //莫队修改
    isi[tl[p]] ? tmp -= !--cnt[pa[tl[p]]] : tmp += !cnt[pa[tl[p]]]++;
    isi[tl[p]] ^= 1;
}

int main() {
    qrd(n), qrd(m);
    bl = ceil(sqrt(2*n));
    for(int i(1);i<=2*n;++i) {
        b[i] = b[i-1];
        if(i>b[i]*bl) {
            ++b[i];
        }
    }
    for(int i(1);i<=n;++i) {
        qrd(a[i]);
        dca[i] = a[i];
    }
    //离散化
    sort(dca+1,dca+n+1);
    int lena = unique(dca+1,dca+n+1) - dca - 1;
    for(int i(1);i<=n;++i) {
        pa[i] = lower_bound(dca+1,dca+lena+1,a[i]) - dca;
    }
    for(int i(1);i<n;++i) {
        int u,v;
        qrd(u), qrd(v);
        adde(u,v), adde(v,u);
    }
    //树剖+欧拉序
    dfs(1);
    lt[1] = 1;
    dfs2(1);
    for(int i(1);i<=m;++i) {
        qry& q(aq[i]);
        int x,y;
        qrd(x), qrd(y);
        int lx = lca(x,y);
        if(tin[x]>tin[y]) {
            x^=y^=x^=y;
        }
        //分类讨论
        if(lx==x) {
            q = {tin[x],tin[y],lx,i};
        } else {
            q = {tout[x],tin[y],lx,i};
        }
    }
    sort(aq+1,aq+m+1);
    //莫队
    int l(1),r(0);
    for(int i(1);i<=m;++i) {
        qry& q(aq[i]);
        while(r<q.r) {
            change(++r);
        }
        while(l>q.l) {
            change(--l);
        }
        while(r>q.r) {
            change(r--);
        }
        while(l<q.l) {
            change(l++);
        }
        if(!cnt[pa[q.lx]]) {    //额外统计lca的贡献
            ++ans[q.i];
        }
        ans[q.i] += tmp;
    }
    for(int i(1);i<=m;++i) {
        printf("%d\n",ans[i]);
    }
    return 0;
}