2023.01.17 模拟赛小结

更好的阅读体验戳此进入

赛时思路

T1

LG-P8280 「MCOI-08」Photoelectric Effect。

有一棵 $n$$n$（$1\le n\le {10}^5$$1\le n\le 10^5$）个点的树以及 $k$$k$（$2\le k\le 5$$2\le k\le 5$）个颜色，根节点为 $1$$1$。同时，给定一个颜色合并函数 $a\otimes b$$a\otimes b$，满足当 $1\le a,b\le k$$1\le a,b\le k$，有 $1\le a\otimes b\le k$$1\le a\otimes b\le k$。

请问有多少个方案对所有点染色，使得当点对 $u,v$$u,v$ 之间没有祖先关系，有：

• $u$$u$ 和 $v$$v$ 最近公共祖先的颜色为点 $u$$u$ 的颜色和点 $v$$v$ 的颜色之并。

答案对 ${10}^9+7$$10^9+7$ 取模。

一个较为显然的 树形DP + 状压DP，复杂度卡的比较满，细节巨多，但是思路较为显然，赛时写了 $2h$$2h$，大样例也过了，然后最后 LemonLime 上 whs 造的数据过了 $90\mathtt{\text{pts}}$$90\texttt{pts}$，但是 Luogu 上几乎全 WA 了，最后找了一下才发现判断叶子节点时 !head[p]->nxt 把根也当成叶子了，也就是如果根只有一个子树那就会寄掉。

然后还有个问题就是 Luogu 上必须把边数开到 $2e6$$2e6$，开到 $1e6$$1e6$ 都不行，这也是一个亟待解决的问题。

当然这里的代码是赛时不太正确的，AC Code 参考下文。

Code

xxxxxxxxxx
152
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
#define MOD (ll)(1e9 + 7)
23
#define S(name, idx) ((name) & (1 << ((idx) - 1)))
24

25
template < typename T = int >
26
inline T read(void);
27

28
struct Edge{
29
    Edge* nxt;
30
    int to;
31
    OPNEW;
32
}ed[210000];
33
ROPNEW;
34
Edge* head[210000];
35

36
int N, K;
37
int Smx;
38
int opt[10][10];
39
struct Node{int S; int col;};
40
basic_string < Node > legal[40];
41
ll dp[110000][40][6];
42
ll merg[40][6];
43

44
void Clear(void){
45
    for(int i = 0; i <= Smx; ++i)legal[i].clear();
46
    for(int i = 0; i <= N; ++i)head[i] = npt;
47
    for(int i = 0; i <= N; ++i)for(int S = 0; S <= Smx; ++S)for(int k = 1; k <= K; ++k)dp[i][S][k] = 0;
48
}
49
void TreeDP(int p = 1, int fa = 0){
50
    for(auto i = head[p]; i; i = i->nxt)if(SON != fa)TreeDP(SON, p);
51
    if(!head[p]->nxt){for(int i = 0; i < K; ++i)dp[p][1 << i][i + 1] = 1; return;}
52
    memset(merg, 0, sizeof merg);
53
    bool isbeg(true);
54
    for(auto i = head[p]; i; i = i->nxt){
55
        if(SON == fa)continue;
56
        if(isbeg){
57
            isbeg = false;
58
            for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)for(int k = 1; k <= K; ++k)(merg[S][j] += dp[SON][S][k]) %= MOD;
59
            // printf("p is %d, after merge, merge is : \n", p);
60
            // for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)
61
            //     cout << "merg[" << i << "][" << bitset < 5 >(S) << "] = " << merg[S][i] << endl;
62
            continue;
63
        }
64
        ll lst[40][6];
65
        for(int S = 0; S <= Smx; ++S)for(int j = 1; j <= K; ++j)lst[S][j] = merg[S][j], merg[S][j] = 0;
66
        ll sum[40]; memset(sum, 0, sizeof sum);
67
        for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)(sum[S] += dp[SON][S][j]) %= MOD;
68
        for(int S1 = 1; S1 <= Smx; ++S1)
69
            for(auto S2 : legal[S1])
70
                (merg[S1 | S2.S][S2.col] += lst[S1][S2.col] * sum[S2.S] % MOD) %= MOD;
71
        // printf("p is %d, after merge, merge is : \n", p);
72
        // for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)
73
        //     cout << "merg[" << i << "][" << bitset < 5 >(S) << "] = " << merg[S][i] << endl;
74
    }
75
    for(int S = 1; S <= Smx; ++S)
76
        for(int i = 1; i <= K; ++i)
77
            (dp[p][S | (1 << (i - 1))][i] += merg[S][i]) %= MOD;
78
}
79

80
int main(){
81
    freopen("color.in", "r", stdin);
82
    freopen("color.out", "w", stdout);
83
    int T = read();
84
    while(T--){
85
        Clear();
86
        N = read(), K = read();
87
        Smx = (1 << K) - 1;
88
        for(int i = 1; i <= K; ++i)for(int j = 1; j <= K; ++j)opt[i][j] = read();
89
        for(int i = 2; i <= N; ++i){
90
            int s = i, t = read();
91
            head[s] = new Edge{head[s], t};
92
            head[t] = new Edge{head[t], s};
93
        }
94
        for(int S1 = Smx; S1; S1 = (S1 - 1) & Smx)
95
            for(int S2 = Smx; S2; S2 = (S2 - 1) & Smx){
96
                int cur(-1);
97
                bool flag(true);
98
                for(int i = 1; i <= K; ++i){
99
                    if(!flag)break;
100
                    for(int j = 1; j <= K; ++j){
101
                        if(!flag)break;
102
                        if(S(S1, i) && S(S2, j)){
103
                            if(opt[i][j] != opt[j][i]){flag = false; break;}
104
                            if(!~cur)cur = opt[i][j];
105
                            else if(opt[i][j] != cur)flag = false;
106
                        }
107
                    }
108
                }if(flag)legal[S1] += Node{S2, cur};
109
            }
110
        // for(int S = 1; S <= Smx; ++S)for(auto S2 : legal[S]){
111
        //     cout << bitset < 5 >(S) << "with" << bitset < 5 >(S2.S) << "  col is" << S2.col << endl;
112
        // }
113
        TreeDP();
114
        // for(int i = 1; i <= N; ++i)for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)
115
        //     cout << "dp[" << i << "][" << j << "][" << bitset < 5 >(S) << "] = " << dp[i][S][j] << endl;
116
        ll ans(0);
117
        for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)(ans += dp[1][S][i]) %= MOD;
118
        printf("%lld\n", ans);
119
    }
120
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
121
    return 0;
122
}
123

124
template < typename T >
125
inline T read(void){
126
    T ret(0);
127
    int flag(1);
128
    char c = getchar();
129
    while(c != '-' && !isdigit(c))c = getchar();
130
    if(c == '-')flag = -1, c = getchar();
131
    while(isdigit(c)){
132
        ret *= 10;
133
        ret += int(c - '0');
134
        c = getchar();
135
    }
136
    ret *= flag;
137
    return ret;
138
}
139

140
/*
141

142
2
143
5 2
144
1 2
145
2 1
146
1 2 1 4
147
5 2
148
1 2
149
1 1
150
1 2 1 4
151

152
*/

T2

LG-P6157 有趣的游戏。

给定 $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。

写了篇题解，内容就放在下文了，错的点是没有考虑到应该维护前 $5$$5$ 大，只维护了 $4$$4$，且常数过大，然后赛时被卡到了 $20\mathtt{\text{pts}}$$20\texttt{pts}$。

Code

xxxxxxxxxx
193
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

23

24
template < typename T = int >
25
inline T read(void);
26

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

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

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

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

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

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

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

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

175
/*
176

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

193
*/

T3

CF1762F Good Pairs。

给定一个 $n$$n$ 个数的序列 $a$$a$ 和一个数 $k$$k$，定义一个 子区间 $[l,r]$$[l,r]$ 是好的，当且仅当这个区间内存在一个 子序列 满足：

• 包含 $a_l$$a_l$ 和 $a_r$$a_r$
• 任意相邻两个数差的绝对值不超过 $k$$k$

请求出所有合法的子区间数量。多组数据，$1\le \sum n\le 5\times {10}^5,0\le k\le {10}^5,1\le a_i\le {10}^5$$1\le \sum n\le 5\times 10^5,\ 0\le k\le 10^5,\ 1\le a_i\le 10^5$。

不会，跳！

T4

CF1774G Segment Covering。

给定 $n$$n$ 个区间 $[x_i,y_i]$$[x_i, y_i]$，保证所有区间均不同。令 $f(l,r)$$f(l, r)$ 表示从 $n$$n$ 个区间中选择偶数个区间使得其求并集后恰为 $[l,r]$$[l, r]$ 的方案数，令 $g(l,r)$$g(l, r)$ 表示从 $n$$n$ 个区间中选择奇数个区间使得其求并集后恰为 $[l,r]$$[l, r]$ 的方案数。给定 $q$$q$ 组询问 $[l_i,r_i]$$[l_i, r_i]$，输出 $f(l_i,r_i)-g(l_i,r_i)$$f(l_i, r_i) - g(l_i, r_i)$，对 $998244353$$998244353$ 取模。

赛时没想出来，确实是一道人类智慧性质题，很有 AGC 的感觉，赛时糊的暴力也挂了。

Code

xxxxxxxxxx
79
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
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
struct Range{int l, r;};
28
Range R[11];
29
int N, Q;
30

31
int main(){
32
    freopen("segment.in", "r", stdin);
33
    freopen("segment.out", "w", stdout);
34
    N = read(), Q = read();
35
    for(int i = 1; i <= N; ++i)R[i].l = read(), R[i].r = read();
36
    sort(R + 1, R + N + 1, [](const Range &a, const Range &b)->bool{return a.l < b.l;});
37
    int Smx = (1 << N) - 1;
38
    while(Q--){
39
        int l = read(), r = read();
40
        ll F(0), G(0);
41
        for(int S = Smx; S; S = (S - 1) & Smx){
42
            int curl(-1), curr(-1);
43
            bool flag(true);
44
            for(int i = 0; i < N; ++i){
45
                if(S & (1 << i)){
46
                    if(!~curl)curl = R[i + 1].l;
47
                    if(!~curr)curr = R[i + 1].r;
48
                    else{
49
                        if(R[i + 1].l > curr)flag = false;
50
                        else curr = R[i + 1].r;
51
                    }
52
                }
53
            }
54
            if(flag && curl == l && curr == r){
55
                if(__builtin_popcount(S) & 1)++G;
56
                else ++F;
57
            }
58
        }
59
        printf("%lld\n", ((F - G) % MOD + MOD) % MOD);
60
    }
61
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
62
    return 0;
63
}
64

65
template < typename T >
66
inline T read(void){
67
    T ret(0);
68
    int flag(1);
69
    char c = getchar();
70
    while(c != '-' && !isdigit(c))c = getchar();
71
    if(c == '-')flag = -1, c = getchar();
72
    while(isdigit(c)){
73
        ret *= 10;
74
        ret += int(c - '0');
75
        c = getchar();
76
    }
77
    ret *= flag;
78
    return ret;
79
}

正解

T1

上文说的差不多了。

Code

xxxxxxxxxx
158
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
#define MOD (ll)(1e9 + 7)
23
#define S(name, idx) ((name) & (1 << ((idx) - 1)))
24

25
template < typename T = int >
26
inline T read(void);
27

28
struct Edge{
29
    Edge* nxt;
30
    int to;
31
    OPNEW;
32
}ed[2100000];
33
ROPNEW;
34
Edge* head[110000];
35

36
int N, K;
37
int Smx;
38
int opt[10][10];
39
struct Node{int S; int col;};
40
basic_string < Node > legal[40];
41
ll dp[110000][40][6];
42
ll merg[40][6];
43

44
void Clear(void){
45
    for(int i = 0; i <= Smx; ++i)legal[i].clear();
46
    for(int i = 0; i <= N; ++i)head[i] = npt;
47
    for(int i = 0; i <= N; ++i)for(int S = 0; S <= Smx; ++S)for(int k = 1; k <= K; ++k)dp[i][S][k] = 0;
48
}
49
void TreeDP(int p = 1, int fa = 0){
50
    for(auto i = head[p]; i; i = i->nxt)if(SON != fa)TreeDP(SON, p);
51
    if(p != 1 && !head[p]->nxt){for(int i = 0; i < K; ++i)dp[p][1 << i][i + 1] = 1; return;}
52
    memset(merg, 0, sizeof merg);
53
    bool isbeg(true);
54
    for(auto i = head[p]; i; i = i->nxt){
55
        if(SON == fa)continue;
56
        if(isbeg){
57
            isbeg = false;
58
            for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)for(int k = 1; k <= K; ++k)(merg[S][j] += dp[SON][S][k]) %= MOD;
59
            // printf("p is %d, after merge, merge is : \n", p);
60
            // for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)
61
            //     cout << "merg[" << i << "][" << bitset < 5 >(S) << "] = " << merg[S][i] << endl;
62
            continue;
63
        }
64
        ll lst[40][6];
65
        for(int S = 0; S <= Smx; ++S)for(int j = 1; j <= K; ++j)lst[S][j] = merg[S][j], merg[S][j] = 0;
66
        ll sum[40]; memset(sum, 0, sizeof sum);
67
        for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)(sum[S] += dp[SON][S][j]) %= MOD;
68
        for(int S1 = 1; S1 <= Smx; ++S1)
69
            for(auto S2 : legal[S1])
70
                (merg[S1 | S2.S][S2.col] += lst[S1][S2.col] * sum[S2.S] % MOD) %= MOD;
71
        // printf("p is %d, after merge, merge is : \n", p);
72
        // for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)
73
        //     cout << "merg[" << i << "][" << bitset < 5 >(S) << "] = " << merg[S][i] << endl;
74
    }
75
    for(int S = 1; S <= Smx; ++S)
76
        for(int i = 1; i <= K; ++i)
77
            (dp[p][S | (1 << (i - 1))][i] += merg[S][i]) %= MOD;
78
    // printf("p = %d\n", p);
79
    // for(int S = 1; S <= Smx; ++S)
80
    //     for(int i = 1; i <= K; ++i){
81
            
82
    //         printf("dp[%d][", i); cout << bitset < 5 >(S); printf("] = %lld\n", dp[p][S][i]);
83
    //     }
84
}
85

86
int main(){
87
    // freopen("color.in", "r", stdin);
88
    // freopen("color.out", "w", stdout);
89
    int T = read();
90
    while(T--){
91
        Clear();
92
        N = read(), K = read();
93
        Smx = (1 << K) - 1;
94
        for(int i = 1; i <= K; ++i)for(int j = 1; j <= K; ++j)opt[i][j] = read();
95
        for(int i = 2; i <= N; ++i){
96
            int s = i, t = read();
97
            head[s] = new Edge{head[s], t};
98
            head[t] = new Edge{head[t], s};
99
        }
100
        for(int S1 = Smx; S1; S1 = (S1 - 1) & Smx)
101
            for(int S2 = Smx; S2; S2 = (S2 - 1) & Smx){
102
                int cur(-1);
103
                bool flag(true);
104
                for(int i = 1; i <= K; ++i){
105
                    if(!flag)break;
106
                    for(int j = 1; j <= K; ++j){
107
                        if(!flag)break;
108
                        if(S(S1, i) && S(S2, j)){
109
                            if(opt[i][j] != opt[j][i]){flag = false; break;}
110
                            if(!~cur)cur = opt[i][j];
111
                            else if(opt[i][j] != cur)flag = false;
112
                        }
113
                    }
114
                }if(flag)legal[S1] += Node{S2, cur};
115
            }
116
        // for(int S = 1; S <= Smx; ++S)for(auto S2 : legal[S]){
117
        //     cout << bitset < 5 >(S) << "with" << bitset < 5 >(S2.S) << "  col is" << S2.col << endl;
118
        // }
119
        TreeDP();
120
        // for(int i = 1; i <= N; ++i)for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)
121
        //     cout << "dp[" << i << "][" << j << "][" << bitset < 5 >(S) << "] = " << dp[i][S][j] << endl;
122
        ll ans(0);
123
        for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)(ans += dp[1][S][i]) %= MOD;
124
        printf("%lld\n", ans);
125
    }
126
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
127
    return 0;
128
}
129

130
template < typename T >
131
inline T read(void){
132
    T ret(0);
133
    int flag(1);
134
    char c = getchar();
135
    while(c != '-' && !isdigit(c))c = getchar();
136
    if(c == '-')flag = -1, c = getchar();
137
    while(isdigit(c)){
138
        ret *= 10;
139
        ret += int(c - '0');
140
        c = getchar();
141
    }
142
    ret *= flag;
143
    return ret;
144
}
145

146
/*
147

148
2
149
5 2
150
1 2
151
2 1
152
1 2 1 4
153
5 2
154
1 2
155
1 1
156
1 2 1 4
157

158
*/

T2

提供一种复杂度正确但常数巨大码量较大的并不优秀的无脑做法，思路来自于模拟赛赛时口糊的，在 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
*/