CTime_Pup_314

不能再颓废了

0%

90509102 NOIP模拟题

发表于 更新于 分类于 阅读次数： Valine：

C

题面描述

树上快速维护位运算

题解

设 \(u\) 和 \(v\) 的有向简单路径构成的集合为 \(S(u,\ v)\) 题意即是求 \[ \sum_{w\in S(u,v)}a_w\ or\ dis(u,\ w) \]

\(dis(u,\ w)\) 表示边数 位运算和倍增结合的神仙题，题解看了好久

首先，题目询问有向路径，我们把路径用 \(lca(u,\ v)\) 分为两半

先考虑向上部分，首先 \(or\) 操作不会使贡献减少，它一定有 \(\sum_{w\in S}a_w\) 的基础贡献，并且对于位 \(k\) 它会增加 \(2^k\) 贡献仅当 \(2^k\ and\ dis(u,w) =\ 2^k\)

我们发现这样和倍增的思想意外的吻合，倍增中的合并是貌似可以在不考虑进位的情况下快速计算增加的贡献

不妨设 \(c_{i,x}\) 表示 \(x\) 到根的路径上满足 \(x\) 的位 \(i\) 为 \(0\) 的个数，\(fa_{i,x}\) 表示 \(x\) 的 \(2^i\) 级祖先

很容易写出转移

\[ \begin{aligned} fa_{i,x}\ &=\ fa_{i-1,fa_{i-1,x}}\ (i>0)\\\\ c_{i,x}\ &=\ c_{i,fa_{x,0}}+[a_x>>k\&1==0]\\ \end{aligned} \]

1
for(int i = 1; i <= 20; ++i) fa[i][x] = fa[i-1][fa[i-1][x]];
1
for(int i = 0; i <= 20; ++i) c[i][x] = c[i][fa[0][x]]+((a[x]>>i&1)==0);

设 \(f_{i,x}\) 表示 \(x\) 向上走 \(2^i-1\) 条边的收益，它经过点集 \(S\)

即

\[ f_{i,x}\ =\ \sum_{w\in S}a_w\ or\ dis(x,\ w) \]

首先边界为 \(f_{0,x}\ =\ a_x\)

考虑转移，设 \(y\ =\ fa_{i-1,x},\ z\ =\ fa_{i,x}\) 则有

\[ f_{i,x}\ =\ f_{i-1,x}+f_{i-1,y}+2^{i-1}(c_{i-1,y}-c_{i-1,z}) \]

其道理蕴含在下面

原来的答案并不会减少所以先把基础贡献相加，而多出的贡献来源于右半部分原本位 \(i-1\) 为 \(0\) 的 \(a\) 却因为相对距离原本多加了 \(2^{i-1}\) 而在 \(i-1\) 产生了贡献，利用前缀和的思想从而得出转移方程

这一过程并不会多算或没有考虑进位，因为对于右半部分最大的相对距离 \(2^{i-1}-1\) 小于 \(2^{i-1}\) 因此不会进位

1
2
for(int i = 1; i <= 20; ++i)
    f[i][x] = f[i-1][x]+f[i-1][fa[i-1][x]]+(1ll<<(i-1))*(c[i-1][fa[i-1][x]]-c[i-1][fa[i][x]]);

预处理出这些后我们考虑怎么查询向上的答案

由于倍增数组，我们无非是对于 \(u\) 到 \(lca\) 的路径长度二进制分解，再向上跳父亲的过程中像上述转移方程一样计算后半部分相对距离增加后对答案的贡献

比如说

我们现在在 \(1\) 号节点到 \(6\) 号节点，可以使用 \(1\) 的倍增数组，因为相对距离的偏移量再之前已经算过了

我们现在可以跳到 \(5\) 号节点，中间累加 \(f_{1,2}\) 的贡献即点集 \(S(1,4)\) 的贡献，同时后半部分 \(S(5,6)\) 再从 \(5\) 出发相对距离增加 \(4\)，即位 \(2\) 由 \(0\) 变为 \(1\) ，类比上述转移，答案增加 \(2^2(cnt_{2,5}-cnt_{2,7})\)

但是我们是从小到大进行二进制分解，还是从大到小是一个问题

我们是必须要避免相对距离增加过程是否有进位的

所以假设从大到小枚举 \(i\) 对于当前 \(2^i\)，而后面的和由等比数列求和得到 \(2^i-1\) 所以没有进位，而逆序枚举就不一样了

所以向上统计时需要这样做

1
2
3
4
5
6
7
8
9
10
11
int64_t queryUp(int u, int tar) // tar 是 lca 的父亲，但最后点集只会到lca，想一想为什么(考虑fa[i][x]和f[i][x]走到节点的不同)
{
    int w = u; int64_t ret = 0;
    for(int i = 20; ~i; --i)
        if(d[fa[i][w]] >= d[tar]) // 从大到小枚举即使贪心的向上条就行了
        {
            ret += f[i][w]; w = fa[i][w];
            ret += (1ll<<i)*(c[i][w]-c[i][tar]);
        }
    return ret;
}

向下差不多就是类比向上了

设 \(g_{i,x}\) 表示 \(x\) 从 \(2^i-1\)级祖先，向下走 \(2^i-1\) 条边的收益

边界为 \(g_{0,x}\ =\ a_x\)

考虑转移，设 \(y\ =\ fa_{i-1,x}\)，则有

\[ g_{i,x}\ =\ g_{i-1,x}+g_{i-1,y}+2^{i-1}(c_{i-1,x}-c_{i-1,y}) \]

转移过程差不多和 \(f\) 一样，只不过产生贡献是左半部分

1
2
for(int i = 1; i <= 20; ++i)
    g[i][x] = g[i-1][x]+g[i-1][fa[i-1][x]]+(1ll<<(i-1))*(c[i-1][x]-c[i-1][fa[i-1][x]]);

我们考虑怎么统计向下路径，标程的想法极富创造性

我们要统计 \(3\) 向下到 \(6\) 的路径，可是相对距离增初始加的就不是 \(2\) 的整数次幂，就非常麻烦

我们考虑把路径的另一半对称上去，使其变为到根节点的直链

这时就相当于从 \(u\) 的 \(dis(u,v)\) 级祖先向下走 \(dis(u,v)\) 步的收益，利用前缀和的思想再减去 从 \(lca\) 的 \(dis(u,lca)\) 级祖先向下走 \(dis(u,lca)\) 步 的收益

这样貌似就是对 \(g\) 做二进制拆分的操作了

但此时 \(i\) 出现了枚举顺序的问题

考虑从\(3\)向上跳到\(5\)的过程，这是 \(S(1,2)\) 的相对路径增加了 \(2\)，贡献增加了 \(2^1(cnt_{1,3}-cnt_{1,1})\)

所以我们再不进位的情况下要求前缀和小与当前值，当从小到大枚举时，前缀和 \(2^i-1\) 小于 \(2^i\)

所以进行如下操作

1
2
3
4
5
6
7
8
9
10
11
int64_t queryDown(int v, int dis)
{
    int w = v; int64_t ret = 0; ++dis; // 和上文的 tar 同理
    for(int i = 0; i <= 20; ++i) // 从小到大枚举
        if(dis>>i&1)
        {
            ret += g[i][w]; 
            ret += (1ll<<i)*(c[i][v]-c[i][w]); w = fa[i][w];
        }
    return ret;
}

完整如下

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <cstdint>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch=='-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 3e5+5, L = 21;
int n, q;
vector<int> edge[N];
int fa[L][N], d[N], a[N];
int64_t g[L][N], f[L][N], c[L][N]; // 由于毒瘤卡常所以小的一维在前
void dfs(int x, int f)
{   
    fa[0][x] = f; d[x] = d[f]+1;
    for(int i = 0; i <= 20; ++i) c[i][x] = c[i][f]+((a[x]>>i&1)==0);
    for(int i = 0; i < edge[x].size(); ++i)
    {
        int y = edge[x][i]; 
        if(y == f) continue;
        dfs(y, x);   
    }
}

int LCA(int x,int y)
{
    if(d[x] < d[y]) swap(x, y);
    for(int i = 20; ~i; --i) if(d[fa[i][x]] >= d[y]) x = fa[i][x];
    if(x == y) return x;
    for(int i = 20; ~i; --i) if(fa[i][x] != fa[i][y]) x = fa[i][x], y = fa[i][y];
    return fa[0][x];
}

int64_t queryUp(int u, int tar)
{
    int w = u; int64_t ret = 0;
    for(int i = 20; ~i; --i)
        if(d[fa[i][w]] >= d[tar])
        {
            ret += f[i][w]; w = fa[i][w];
            ret += (1ll<<i)*(c[i][w]-c[i][tar]);
        }
    return ret;
}

int64_t queryDown(int v, int dis)
{
    int w = v; int64_t ret = 0; ++dis;
    for(int i = 0; i <= 20; ++i)
        if(dis>>i&1)
        {
            ret += g[i][w]; 
            ret += (1ll<<i)*(c[i][v]-c[i][w]); w = fa[i][w];
        }
    return ret;
}

int main()
{
    n = read(); q = read();
    for(int x = 1; x <= n; ++x) f[0][x] = g[0][x] = a[x] = read();
    for(int i = 1; i < n; ++i)
    {
        int x = read(), y = read();
        edge[x].push_back(y); 
        edge[y].push_back(x);
    }
    dfs(1, 0);
    for(int i = 1; i <= 20; ++i)
        for(int x = 1; x <= n; ++x)
        {
            fa[i][x] = fa[i-1][fa[i-1][x]];
            f[i][x] = f[i-1][x]+f[i-1][fa[i-1][x]]+(1ll<<(i-1))*(c[i-1][fa[i-1][x]]-c[i-1][fa[i][x]]);
            g[i][x] = g[i-1][x]+g[i-1][fa[i-1][x]]+(1ll<<(i-1))*(c[i-1][x]-c[i-1][fa[i-1][x]]);          
        }
    while(q--)
    {
        int u = read(), v = read();
        int uv = LCA(u, v);
        printf("%lld\n", queryUp(u, fa[0][uv])+queryDown(v, d[u]+d[v]-2*d[uv])-queryDown(uv, d[u]-d[uv]));
    }
    return 0;
}