音无彩名给你一个数组 AA,以及一棵 nn 个节点的树,每个点有一个颜色,颜色为 11 到 xx 的整数。 有 mm 次查询,每次查询树上只保留 [l,r][l,r] 内的所有节点,设一个极大连通块中出现奇数次数的颜色个数为 tt,则其对答案的贡献为 A_tA t ,即答案是所有连通块贡献的和,询问间互相独立。 输入格式 第一行三个用空格隔开的数 n,m,xn,m,x。 第二行 nn 个数表示每个点的颜色。 之后 n-1n−1 行每行两个用空格隔开的数 x,yx,y 表示一条边。 之后一行 x+1x+1 个数表示 A_0A 0 到 A_xA x 。 之后 mm 行,每行两个用空格隔开的数 l,rl,r 表示一次询问。 输出格式 输出 mm 行,每行一个数表示这次询问的答案。 输入输出样例 输入 #1复制 6 3 5 1 1 4 5 1 4 1 2 2 3 3 4 4 5 5 6 1 1 4 5 1 4 1 1 4 5 1 4 输出 #1复制 1 4 4代码
时间: 2024-01-17 12:03:41 浏览: 25
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 200010, BLOCK = 320;
int n, m, x;
int w[N], h[N], e[M], ne[M], idx;
int a[N], cnt[N], appear[N];
int stk[N], top;
int id[N], dep[N], sz[N], son[N], fa[N], tot;
int lg[N], st[N][17], res;
int ans[N];
struct Query {
int l, r, id;
bool operator< (const Query& other) const {
return id == other.id ? r < other.r : id < other.id;
}
}q[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs1(int u, int father, int depth) {
fa[u] = father, dep[u] = depth, sz[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == father) continue;
dfs1(j, u, depth + 1);
sz[u] += sz[j];
if (sz[j] > sz[son[u]]) son[u] = j;
}
}
void dfs2(int u, int t) {
top ++, id[u] = ++ tot;
a[id[u]] = w[u];
if (!son[u]) {
for (int i = 1; i <= top; i ++ ) {
cnt[a[id[stk[i]]]] ++;
appear[a[id[stk[i]]]] ^= 1;
if (appear[a[id[stk[i]]]]) res += (cnt[a[id[stk[i]]]] & 1) ? 1 : -1;
}
st[id[u]][0] = res;
for (int i = 1; i <= lg[top]; i ++ )
st[id[u]][i] = max(st[id[u] + (1 << i - 1)][i - 1], st[id[u]][i - 1]);
for (int i = 1; i <= top; i ++ ) {
cnt[a[id[stk[i]]]] --;
appear[a[id[stk[i]]]] ^= 1;
}
}
else dfs2(son[u], t);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa[u] || j == son[u]) continue;
dfs2(j, j);
}
if (top == t) top --;
}
int query(int l, int r) {
int k = lg[r - l + 1];
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m >> x;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i < n; i ++ ) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
for (int i = 0; i <= x; i ++ ) cin >> a[i];
dfs1(1, -1, 1);
for (int i = 2; i <= n; i ++ ) lg[i] = lg[i >> 1] + 1;
dfs2(1, 1);
for (int i = 0; i < m; i ++ ) {
int l, r;
cin >> l >> r;
int t = id[l] + sz[l] - 1;
q[i] = {id[l], t, t / BLOCK};
ans[i] = 0;
}
sort(q, q + m);
int l = 1, r = 0;
for (int i = 0; i < m; i ++ ) {
int ql = q[i].l, qr = q[i].r;
while (l < ql) {
cnt[a[id[stk[l]]]] --;
appear[a[id[stk[l]]]] ^= 1;
if (appear[a[id[stk[l]]]]) res += (cnt[a[id[stk[l]]]] & 1) ? 1 : -1;
l ++;
}
while (l > ql) {
l --;
cnt[a[id[stk[l]]]] ++;
appear[a[id[stk[l]]]] ^= 1;
if (appear[a[id[stk[l]]]]) res += (cnt[a[id[stk[l]]]] & 1) ? 1 : -1;
}
while (r < qr) {
r ++;
cnt[a[id[stk[r]]]] ++;
appear[a[id[stk[r]]]] ^= 1;
if (appear[a[id[stk[r]]]]) res += (cnt[a[id[stk[r]]]] & 1) ? 1 : -1;
}
while (r > qr) {
cnt[a[id[stk[r]]]] --;
appear[a[id[stk[r]]]] ^= 1;
if (appear[a[id[stk[r]]]]) res += (cnt[a[id[stk[r]]]] & 1) ? 1 : -1;
r --;
}
for (int j = 0; j <= x; j ++ ) {
if (q[i].l <= id[son[j]] && id[son[j]] + sz[son[j]] - 1 <= q[i].r) {
ans[q[i].id] = max(ans[q[i].id], a[j]);
}
else {
int tmp = query(q[i].l, q[i].r);
if (a[j] + tmp <= x) ans[q[i].id] = max(ans[q[i].id], a[j] + tmp);
}
}
}
for (int i = 0; i < m; i ++ ) cout << ans[i] << '\n';
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![bin](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)