LG-P6157 有趣的游戏 Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$ 个点的树，存在点权 $w_i$$w_i$，独立询问每次可能为单点修改点权，可能给出两点，$A$$A$ 在树上两点最短路径上选择两个点 $x,y$$x, y$ 最大化 $w_{x}mod{w}_y$$w_x \bmod{w_y}$，后者在树上选择非 $x,y$$x, y$ 的两点同样最大化上式，对于每次询问求出 $A$$A$ 最大的值，并求出此时 $B$$B$ 最大的值，$A$$A$ 无法选择则输出 -1。

Solution

提供一种复杂度正确但常数巨大码量较大的并不优秀的无脑做法，思路来自于模拟赛赛时口糊的，在 Luogu 上可以通过，但赛时在 LemonLime 测的时候大概是因为常数原因被卡的就剩 $20\mathtt{\text{pts}}$$20\texttt{pts}$。

首先我们不难想到 $w_{x}mod{w}_y$$w_x \bmod{w_y}$ 即为链上次小值。这个不难证明，若我们选择最大值，那么其对较小值取模后一定小于较小值，而若我们选择次大值对最大值取模那么可以直接保留次小值。

然后呢最开始我看这道题没太仔细，以为 $B$$B$ 也是在链上找，于是考虑的是维护次次小和次次次小保留次次次小，当然这个是大错特错的，不仅没有考虑 $B$$B$ 是树上的，还没有考虑 $A$$A$ 不能重复权值但 $B$$B$ 可以。

于是在我发现问题后就尝试优化这个思路，最终的过程大概是这样的：

首先树剖显然，然后线段树上维护区间的不可重复的前 $5$$5$ 大值，以及最多重复一次（即有两个）的前 $5$$5$ 大值。然后对于合并子区间，我们考虑直接维护结构体然后重载 +，实现上用一个 basic_string 存子节点所有值然后排序并各种特判细节做一下即可，不难发现超大的常数就是卡在这里了，这东西某种意义上来讲可以认为其为 $O(1)$$O(1)$ 的，但是实际上个人感觉平均大概有个 $10$$10$ 左右的常数。

然后修改较为简单不再赘述，对于查询直接按照树剖查询并合并，对于不能重复的前 $5$$5$ 大取其第二大作为 $A$$A$ 的答案，不存在则输出 -1。然后我们要再次查询整棵树的结果，在可重复两次的前 $5$$5$ 大中删去 $A$$A$ 的两个答案，此时不难理解为什么维护的是可以重复两次的。然后此时还需要分类讨论，如果结果不够说明只能找到两个相同的数，这样结果为 $0$$0$，如果最终剩下三个数且前两个为 $0$$0$，那么说明原来的为 $a>b>c=d>e$$a \gt b \gt c = d \gt e$，然后 $a,b$$a, b$ 被删除，此时如果我们不维护 $e$$e$ 答案将变为 $0$$0$，这也就是为什么我们要维护前 $5$$5$ 大而不是 $4$$4$，显然此时答案应为 $e$$e$。同时因为题里没有说 $B$$B$ 取不了的情况，且不难想到只要 $n\ge 4$$n \ge 4$ 那么 $B$$B$ 一定可以拿，所以姑且可以认为题目保证了 $n\ge 4$$n \ge 4$。

当然这里也浅提一下，如果用 multiset 维护 $B$$B$ 的话就只需要维护最大和次大就可以了，常数小且好写，也不知道我模拟赛的时候为什么没想到，估计是开始读错题之后先入为主了。

Code

xxxxxxxxxx
192
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
struct Edge{
26
    Edge* nxt;
27
    int to;
28
    OPNEW;
29
}ed[210000];
30
ROPNEW;
31
Edge* head[110000];
32

33
int N, Q;
34
ll w[110000];
35
int dep[110000], dfn[110000], hson[110000], siz[110000], ffa[110000], tp[110000], idx[110000];
36

37
void dfs_pre(int p = 1, int fa = 0){
38
    dep[p] = dep[fa] + 1;
39
    siz[p] = 1;
40
    ffa[p] = fa;
41
    for(auto i = head[p]; i; i = i->nxt){
42
        if(SON == fa)continue;
43
        dfs_pre(SON, p);
44
        siz[p] += siz[SON];
45
        if(siz[hson[p]] < siz[SON])hson[p] = SON;
46
    }
47
}
48
void dfs_make(int p = 1, int top = 1){
49
    tp[p] = top;
50
    static int cdfn(0);
51
    dfn[p] = ++cdfn;
52
    idx[cdfn] = p;
53
    if(hson[p])dfs_make(hson[p], top);
54
    for(auto i = head[p]; i; i = i->nxt)
55
        if(SON != ffa[p] && SON != hson[p])
56
            dfs_make(SON, SON);
57
}
58

59
struct Node{
60
    ll v[6], vu[6]; //v_max_with_2, v_unique
61
    Node(void){memset(v, 0, sizeof v), memset(vu, 0, sizeof vu);}
62
    friend Node operator + (const Node &a, const Node &b){
63
        Node ret;
64
        basic_string < ll > values;
65
        for(int i = 1; i <= 5; ++i){
66
            if(a.v[i])values += a.v[i];
67
            if(b.v[i])values += b.v[i];
68
        }sort(values.begin(), values.end(), greater < ll >());
69
        for(auto it = values.begin(); it != values.end() && next(it) != values.end() && next(it, 2) != values.end();)
70
            if(*it == *next(it) && *next(it) == *next(it, 2))it = values.erase(it);
71
            else advance(it, 1);
72
        for(int i = 1; i <= 5; ++i)
73
            ret.v[i] = (int)values.size() >= i ? values.at(i - 1) : 0;
74
        values.clear();
75
        for(int i = 1; i <= 5; ++i){
76
            if(a.vu[i])values += a.vu[i];
77
            if(b.vu[i])values += b.vu[i];
78
        }sort(values.begin(), values.end(), greater < ll >());
79
        values.erase(unique(values.begin(), values.end()), values.end());
80
        for(int i = 1; i <= 5; ++i)
81
            ret.vu[i] = (int)values.size() >= i ? values.at(i - 1) : 0;
82
        return ret;
83
    }
84
};
85

86
class SegTree{
87
private:
88
    Node mx[110000 << 2];
89
    #define LS (p << 1)
90
    #define RS (LS | 1)
91
    #define MID ((gl + gr) >> 1)
92
public:
93
    void Pushup(int p){
94
        mx[p] = mx[LS] + mx[RS];
95
    }
96
    void Build(int p = 1, int gl = 1, int gr = N){
97
        if(gl == gr)return mx[p].v[1] = mx[p].vu[1] = w[idx[gl = gr]], void();
98
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
99
        Pushup(p);
100
    }
101
    void Modify(int id, int v, int p = 1, int gl = 1, int gr = N){
102
        if(gl == gr)return mx[p].v[1] += v, mx[p].vu[1] += v, void();
103
        if(id <= MID)Modify(id, v, LS, gl, MID);
104
        else Modify(id, v, RS, MID + 1, gr);
105
        Pushup(p);
106
    }
107
    Node Query(int l, int r, int p = 1, int gl = 1, int gr = N){
108
        // printf("Querying l = %d, r = %d\n", l, r);
109
        if(l <= gl && gr <= r)return mx[p];
110
        if(gr < l || r < gl)return Node();
111
        return Query(l, r, LS, gl, MID) + Query(l, r, RS, MID + 1, gr);
112
    }
113
}st;
114

115
void Make(int s, int t){
116
    Node cur;
117
    while(tp[s] != tp[t]){
118
        if(dep[tp[s]] < dep[tp[t]])swap(s, t);
119
        cur = cur + st.Query(dfn[tp[s]], dfn[s]);
120
        s = ffa[tp[s]];
121
    }if(dep[s] < dep[t])swap(s, t);
122
    cur = cur + st.Query(dfn[t], dfn[s]);
123
    if(!cur.vu[1] || !cur.vu[2]){printf("-1\n"); return;}
124
    Node ret = st.Query(1, N);
125
    basic_string < ll > tmp;
126
    for(int i = 1; i <= 5; ++i)if(ret.v[i])tmp += ret.v[i];
127
    for(int i = 1; i <= 2; ++i)
128
        if(find(tmp.begin(), tmp.end(), cur.vu[i]) != tmp.end())
129
            tmp.erase(find(tmp.begin(), tmp.end(), cur.vu[i]));
130
    if((int)tmp.size() < 2 || ((int)tmp.size() == 2 && tmp.at(0) == tmp.at(1))){printf("%lld 0\n", cur.vu[2]); return;}
131
    if(tmp.size() == 3 && tmp.at(0) == tmp.at(1)){printf("%lld %lld\n", cur.vu[2], tmp.at(2)); return;}
132
    printf("%lld %lld\n", cur.vu[2], tmp.at(0) == tmp.at(1) ? tmp.at(2) : tmp.at(1));
133
    // for(int i = 1; i <= 5; ++i)printf("mxchain mxvu[%d] = %lld\n", i, cur.vu[i]);
134
    // for(int i = 1; i <= 5; ++i)printf("mxtree mxv[%d] = %lld\n", i, ret.v[i]);
135
}
136

137
int main(){
138
    // freopen("game.in", "r", stdin);
139
    // freopen("game.out", "w", stdout);
140
    N = read();
141
    for(int i = 1; i <= N - 1; ++i){
142
        int s = read(), t = read();
143
        head[s] = new Edge{head[s], t};
144
        head[t] = new Edge{head[t], s};
145
    }dfs_pre(), dfs_make();
146
    for(int i = 1; i <= N; ++i)w[i] = read();
147
    st.Build();
148
    Q = read();
149
    while(Q--){
150
        int opt = read(), x = read(), y = read();
151
        if(opt == 0)st.Modify(dfn[x], y);
152
        else Make(x, y);
153
    }
154
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
155
    return 0;
156
}
157

158
template < typename T >
159
inline T read(void){
160
    T ret(0);
161
    int flag(1);
162
    char c = getchar();
163
    while(c != '-' && !isdigit(c))c = getchar();
164
    if(c == '-')flag = -1, c = getchar();
165
    while(isdigit(c)){
166
        ret *= 10;
167
        ret += int(c - '0');
168
        c = getchar();
169
    }
170
    ret *= flag;
171
    return ret;
172
}
173

174
/*
175

176
7
177
1 2
178
2 3
179
2 5
180
1 5
181
5 6
182
5 7
183
5 5 3 2 1 5 3
184
6
185
1 3 5
186
1 2 5
187
1 2 1
188
0 2 1
189
1 2 5
190
1 2 1
191

192
*/

UPD

update-2023_01_17 初稿