LG-P6157 有趣的游戏 Solution
目录更好的阅读体验戳此进入
题面
给定 $ n $ 个点的树，存在点权 $ w_i \(，独立询问每次可能为单点修改点权，可能给出两点，\) A $ 在树上两点最短路径上选择两个点 $ x, y $ 最大化 $ w_x \bmod{w_y} $，后者在树上选择非 $ x, y $ 的两点同样最大化上式，对于每次询问求出 $ A $ 最大的值，并求出此时 $ B $ 最大的值，$ A $ 无法选择则输出 -1。
Solution
提供一种复杂度正确但常数巨大码量较大的并不优秀的无脑做法，思路来自于模拟赛赛时口糊的，在 Luogu 上可以通过，但赛时在 LemonLime 测的时候大概是因为常数原因被卡的就剩 $ 20\texttt{pts} $。
首先我们不难想到 $ w_x \bmod{w_y} $ 即为链上次小值。这个不难证明，若我们选择最大值，那么其对较小值取模后一定小于较小值，而若我们选择次大值对最大值取模那么可以直接保留次小值。
然后呢最开始我看这道题没太仔细，以为 $ B $ 也是在链上找，于是考虑的是维护次次小和次次次小保留次次次小，当然这个是大错特错的，不仅没有考虑 $ B $ 是树上的，还没有考虑 $ A $ 不能重复权值但 $ B $ 可以。
于是在我发现问题后就尝试优化这个思路，最终的过程大概是这样的：
首先树剖显然，然后线段树上维护区间的不可重复的前 $ 5 $ 大值，以及最多重复一次（即有两个）的前 $ 5 $ 大值。然后对于合并子区间，我们考虑直接维护结构体然后重载 +，实现上用一个 basic_string 存子节点所有值然后排序并各种特判细节做一下即可，不难发现超大的常数就是卡在这里了，这东西某种意义上来讲可以认为其为 $ O(1) $ 的，但是实际上个人感觉平均大概有个 $ 10 $ 左右的常数。
然后修改较为简单不再赘述，对于查询直接按照树剖查询并合并，对于不能重复的前 $ 5 $ 大取其第二大作为 $ A $ 的答案，不存在则输出 -1。然后我们要再次查询整棵树的结果，在可重复两次的前 $ 5 $ 大中删去 $ A $ 的两个答案，此时不难理解为什么维护的是可以重复两次的。然后此时还需要分类讨论，如果结果不够说明只能找到两个相同的数，这样结果为 $ 0 $，如果最终剩下三个数且前两个为 $ 0 $，那么说明原来的为 $ a \gt b \gt c = d \gt e $，然后 $ a, b $ 被删除，此时如果我们不维护 $ e $ 答案将变为 $ 0 $，这也就是为什么我们要维护前 $ 5 $ 大而不是 $ 4 $，显然此时答案应为 $ e $。同时因为题里没有说 $ B $ 取不了的情况，且不难想到只要 $ n \ge 4 $ 那么 $ B $ 一定可以拿，所以姑且可以认为题目保证了 $ n \ge 4 $。
当然这里也浅提一下，如果用 multiset 维护 $ B $ 的话就只需要维护最大和次大就可以了，常数小且好写，也不知道我模拟赛的时候为什么没想到，估计是开始读错题之后先入为主了。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template < typename T = int >
inline T read(void);
struct Edge{
Edge* nxt;
int to;
OPNEW;
}ed[210000];
ROPNEW;
Edge* head[110000];
int N, Q;
ll w[110000];
int dep[110000], dfn[110000], hson[110000], siz[110000], ffa[110000], tp[110000], idx[110000];
void dfs_pre(int p = 1, int fa = 0){
dep[p] = dep[fa] + 1;
siz[p] = 1;
ffa[p] = fa;
for(auto i = head[p]; i; i = i->nxt){
if(SON == fa)continue;
dfs_pre(SON, p);
siz[p] += siz[SON];
if(siz[hson[p]] < siz[SON])hson[p] = SON;
}
}
void dfs_make(int p = 1, int top = 1){
tp[p] = top;
static int cdfn(0);
dfn[p] = ++cdfn;
idx[cdfn] = p;
if(hson[p])dfs_make(hson[p], top);
for(auto i = head[p]; i; i = i->nxt)
if(SON != ffa[p] && SON != hson[p])
dfs_make(SON, SON);
}
struct Node{
ll v[6], vu[6]; //v_max_with_2, v_unique
Node(void){memset(v, 0, sizeof v), memset(vu, 0, sizeof vu);}
friend Node operator + (const Node &a, const Node &b){
Node ret;
basic_string < ll > values;
for(int i = 1; i <= 5; ++i){
if(a.v[i])values += a.v[i];
if(b.v[i])values += b.v[i];
}sort(values.begin(), values.end(), greater < ll >());
for(auto it = values.begin(); it != values.end() && next(it) != values.end() && next(it, 2) != values.end();)
if(*it == *next(it) && *next(it) == *next(it, 2))it = values.erase(it);
else advance(it, 1);
for(int i = 1; i <= 5; ++i)
ret.v[i] = (int)values.size() >= i ? values.at(i - 1) : 0;
values.clear();
for(int i = 1; i <= 5; ++i){
if(a.vu[i])values += a.vu[i];
if(b.vu[i])values += b.vu[i];
}sort(values.begin(), values.end(), greater < ll >());
values.erase(unique(values.begin(), values.end()), values.end());
for(int i = 1; i <= 5; ++i)
ret.vu[i] = (int)values.size() >= i ? values.at(i - 1) : 0;
return ret;
}
};
class SegTree{
private:
Node mx[110000 << 2];
#define LS (p << 1)
#define RS (LS | 1)
#define MID ((gl + gr) >> 1)
public:
void Pushup(int p){
mx[p] = mx[LS] + mx[RS];
}
void Build(int p = 1, int gl = 1, int gr = N){
if(gl == gr)return mx[p].v[1] = mx[p].vu[1] = w[idx[gl = gr]], void();
Build(LS, gl, MID), Build(RS, MID + 1, gr);
Pushup(p);
}
void Modify(int id, int v, int p = 1, int gl = 1, int gr = N){
if(gl == gr)return mx[p].v[1] += v, mx[p].vu[1] += v, void();
if(id <= MID)Modify(id, v, LS, gl, MID);
else Modify(id, v, RS, MID + 1, gr);
Pushup(p);
}
Node Query(int l, int r, int p = 1, int gl = 1, int gr = N){
// printf("Querying l = %d, r = %d\n", l, r);
if(l <= gl && gr <= r)return mx[p];
if(gr < l || r < gl)return Node();
return Query(l, r, LS, gl, MID) + Query(l, r, RS, MID + 1, gr);
}
}st;
void Make(int s, int t){
Node cur;
while(tp[s] != tp[t]){
if(dep[tp[s]] < dep[tp[t]])swap(s, t);
cur = cur + st.Query(dfn[tp[s]], dfn[s]);
s = ffa[tp[s]];
}if(dep[s] < dep[t])swap(s, t);
cur = cur + st.Query(dfn[t], dfn[s]);
if(!cur.vu[1] || !cur.vu[2]){printf("-1\n"); return;}
Node ret = st.Query(1, N);
basic_string < ll > tmp;
for(int i = 1; i <= 5; ++i)if(ret.v[i])tmp += ret.v[i];
for(int i = 1; i <= 2; ++i)
if(find(tmp.begin(), tmp.end(), cur.vu[i]) != tmp.end())
tmp.erase(find(tmp.begin(), tmp.end(), cur.vu[i]));
if((int)tmp.size() < 2 || ((int)tmp.size() == 2 && tmp.at(0) == tmp.at(1))){printf("%lld 0\n", cur.vu[2]); return;}
if(tmp.size() == 3 && tmp.at(0) == tmp.at(1)){printf("%lld %lld\n", cur.vu[2], tmp.at(2)); return;}
printf("%lld %lld\n", cur.vu[2], tmp.at(0) == tmp.at(1) ? tmp.at(2) : tmp.at(1));
// for(int i = 1; i <= 5; ++i)printf("mxchain mxvu[%d] = %lld\n", i, cur.vu[i]);
// for(int i = 1; i <= 5; ++i)printf("mxtree mxv[%d] = %lld\n", i, ret.v[i]);
}
int main(){
// freopen("game.in", "r", stdin);
// freopen("game.out", "w", stdout);
N = read();
for(int i = 1; i <= N - 1; ++i){
int s = read(), t = read();
head[s] = new Edge{head[s], t};
head[t] = new Edge{head[t], s};
}dfs_pre(), dfs_make();
for(int i = 1; i <= N; ++i)w[i] = read();
st.Build();
Q = read();
while(Q--){
int opt = read(), x = read(), y = read();
if(opt == 0)st.Modify(dfn[x], y);
else Make(x, y);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/*
7
1 2
2 3
2 5
1 5
5 6
5 7
5 5 3 2 1 5 3
6
1 3 5
1 2 5
1 2 1
0 2 1
1 2 5
1 2 1
*/
UPD
update-2023_01_17 初稿
标签：LG,110000,P6157,int,题解,void,SON,values,mx From： https://www.cnblogs.com/tsawke/p/17124341.html