【赛题整理】[NOIP2018/CSP2019]题目整理

大概是重做了一下 NOIP2018/CSP2019 两年的全部题目?

感觉当时场上没 A 掉的题,放到现在做总是感觉有点心理阴影emm

Anyway, 只用真正告别过去才能走向未来。你说,对吧?

题目排序为按时间排序。题面看心情加(

NOIP2018

A 铺设道路

考场上并没想到正解。读完题之后觉得每次一定都是选当前段内最小的那个高度来操作,所以就用线段树套了个分治;后来又发现只有询问,于是就变成了 ST 表套了个分治。最后…大概是线性的吧。(但其实大家写的 ST 表都不是线性的)。

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void work(int l, int r, int delta){
if (l > r) return ;
int P = query(l, r) ;
int L = l, R = r ;
while (L < R){
int mid = (L + R) >> 1 ;
if (query(L, mid) == P) R = mid ;
else L = mid + 1 ;
}
int W = L ;
Ans += (base[W] - delta), delta += (base[W] - delta) ;
if (l == r) return ; work(l, W - 1, delta), work(W + 1, r, delta) ;
}

B 货币系统

无脑背包题。感觉两年前的自己真的是菜的一匹…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main(){
cin >> T ;
while (T --){
N = qr(), ans = 0 ;
memset(dp, 0, sizeof(dp)) ;
int i, j, k, o, mxm = 0 ; dp[0] = 1 ;
for (i = 1 ; i <= N ; ++ i)
base[i] = qr(), mxm = max(base[i], mxm) ;
sort(base + 1, base + N + 1, comp) ;
for (i = 1 ; i <= N ; ++ i){
memset(dp, 0, sizeof(dp)), dp[0] = 1 ;
for (k = 1 ; k <= N ; ++ k)
if (i != k && base[k] != -1)
for (j = base[k] ; j <= mxm ; ++ j)
dp[j] |= dp[j - base[k]] ;
if (dp[base[i]]) base[i] = -1 ;
}
for (i = 1 ; i <= N ; ++ i) ans += (bool)(base[i] == -1) ;
printf("%d\n", N - ans) ;
}
return 0 ;
}

C 赛道修建

用 $m$ 条不相交的链覆盖一棵树,最大化长度最小的链。

$2 \leq n \leq 5 \times 10^{4}, 1 \leq m \leq n-1$。

当时考场上写的是

1
2
3
4
5
6
7
if (N <= 2000){
for (int i = 1 ; i <= N ; ++ i)
for (int j = 1 ; j < i ; ++ j)
if (i == j) continue ;
else FFF = LCA(i, j), Ans = max(Ans, Sum[i] + Sum[j] - 2 * Sum[FFF]) ;
if (M > 1) Ans = Ans / M + rand()%(Ans / (M - 1));
}

……也不知道自己咋想的。

然后这次复盘的时候还读错了题,读成了「必须要把全部的边都覆盖」,觉得这种二维限制的怎么可能去二分…感到十分弱智。

之后就变成了考虑二分答案,是否可以选 $\geq m$ 条 $\geq val$ 的边不相交链。感觉似乎是可以 bottom to top 地 dp 一波顺便转移一下没有闭合的链。

这题确实很水,这个贪心已经自然到证都不用证的地步了 233。

一开始打算用 vector 维护。发现需要支持删除和排序就换成了 set。然后还有 multiset 的一些细节没有注意。多亏了 zay,不然我又要调上一年…还有很多其他的细节没有注意,感觉在考场上势必还是要挂分。慢慢练吧。

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
typedef multiset <int> sint ;

int s, g ;
int n, m ;
int f[N] ;
bool vis[N] ;
sint chain[N] ;

void dfs(int x, int fa, int w){
sint t ; t.clear() ;
for (int k = head[x] ; k ; k = next(k)){
if (to(k) == fa) continue ; int z ;
dfs(to(k), x, w) ; f[x] += f[to(k)] ;
z = (*chain[to(k)].begin()) + val(k) ;
if (z >= w) ++ f[x] ; else t.insert(z) ;
// cout << x << " & " << (*chain[to(k)].begin()) + val(k) << " " ;
}
// puts("") ;
// cout << x << " " << t.size() << '\n' ;
if (t.empty())
return void(chain[x].insert(0)) ;
auto s = t.begin() ;
while (s != t.end()){
int p = w - (*s) ;
if (p < 0) break ;
auto q = t.lower_bound(p) ;
if (q == s) ++ q ;
if (q == t.end()) { ++ s ; continue ; }
t.erase(q) ; s = t.erase(s), ++ f[x] ;
}
if (t.empty()) chain[x].insert(0) ;
else chain[x].insert(*(-- t.end())) ;
}
bool check(int x){
for (int i = 1 ; i <= n ; ++ i)
chain[i].clear(), f[i] = 0 ;
dfs(1, 0, x) ; //debug(f, 1, n) ;
return (f[1] >= m) ;
}
int main(){
cin >> n >> m ;
int x, y, z, l = 10000, r = 0, mid, ans ;
for (int i = 1 ; i < n ; ++ i){
x = qr() ; y = qr() ; z = qr() ;
add_e(x, y, z), add_e(y, x, z) ;
r += z ; chkmin(l, z) ;
}
while (l <= r){
mid = (l + r) >> 1 ;
if (check(mid))
ans = mid, l = mid + 1 ;
else r = mid - 1 ;
}
cout << ans << '\n' ; return 0 ;
}

D 旅行

给出一棵树或者一棵基环树,求字典序最小的dfs序。

The original data range : $1\le n\le 5\times 10^3,n-1\leq m\leq n$ 。

The extra data range: $1\le n\le 3\times 10^5,n-1\leq m\leq n$。

考虑如果是树的话显然是可以直接贪的。基环树的话就只需要枚举断哪一条边即可。注意断的边不能是桥边。

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
int find(int x){
return x == fa[x] ? x : fa[x] = find(fa[x]) ;
}
void dfs1(int u, int fa){
sz[u] = 1 ;
for (int k = head[u] ; k ; k = next(k))
if (to(k) != fa && !del[k]){
dfs1(to(k), u),
sz[u] += sz[to(k)],
son[u].push_back(to(k)) ;
}
}
void dfs2(int u, int fa){
int j = 1, k ; o[++ res] = u ;
for (auto k : son[u]) dfs2(k, u) ;
}
bool Compare(int *x, int *y){
for (int i = 1 ; i <= N ; ++ i)
if (x[i] < y[i]) return 1 ;
else if (x[i] > y[i]) return 0 ;
return 0 ;
}
int main(){
cin >> N >> M ; int i, u, v ;
memset(ans, 63, sizeof(ans)) ;
for (i = 1 ; i <= M ; ++ i)
u = qr(), v = qr(), add(u, v) ;
if (M == N - 1){
dfs1(1, 0) ;
for (i = 1 ; i <= N ; ++ i)
sort(son[i].begin(), son[i].end()) ;
dfs2(1, 0) ; memcpy(ans, o, sizeof(o)) ;
}
else
for (int i = 1 ; i <= cnt ; i += 2){
int ctn = 0 ;
for (int j = 1 ; j <= N ; ++ j)
fa[j] = j ; del[i] = del[i + 1] = 1 ;
for (int j = 1 ; j <= cnt ; j += 2){
if (del[j]) continue ;
int f1 = find(fr(j)) ;
int f2 = find(to(j)) ;
if (f1 != f2) fa[f1] = f2 ;
}
for (int j = 1 ; j <= N ; ++ j)
ctn = ctn + (bool)(fa[j] == j) ;
if (ctn == 1) {
dfs1(1, 0) ;
for (int j = 1 ; j <= N ; ++ j)
sort(son[j].begin(), son[j].end()) ;
dfs2(1, 0) ;
for (int j = 1 ; j <= N ; ++ j) son[j].clear() ;
if (Compare(o, ans))
memcpy(ans, o, sizeof(o)) ;
}
del[i] = del[i + 1] = 0 ; res = 0 ;
}
for (i = 1 ; i <= N ; ++ i)
printf("%d ", ans[i]) ; return 0 ;
}

然后考虑更快一点怎么做。发现就是一个弱智贪心。然后就没有然后了。

upd: 香,真香。所谓「弱智贪心」我愣是从 $14:00$ 写到 $20:30$ 。

大概就是一开始觉得,对于当前环,设环里面离 $1$ 最近的一个点 $k$ 是这个环的,那么他一定有两个儿子都在环上,称这两个儿子中较小的那个为左儿子较大的为右儿子。那么要走肯定会走左儿子(这里设为走 $x$),并且断的地方一定是左儿子向下找的途中第一个比右儿子大的点 $z$,将 $z$ 留给右儿子那条链,因为这时先走右儿子一定会更优。

然而这是错的。由于上文钦定了一定要经过 $z$ 之上的点,所以环上所有深度 $>dep_z$ 点的外向枝在回溯时是必须要走的,并且是走完 $z$ 之后就需要接着走。那么如果外向枝中存在点的编号比 $z$ 大,就不如先走 $z$ 再回溯,因为 $z$ 之后紧接的都是比 $z$ 大的。然后想到这里,我大概是用一个值 $v$ 表示从左儿子走到当前点 $z$,沿途外向枝中最大的点的编号。注意细节,如果外向枝中的某些点比当前点要小,那必然是先走外向枝再走现在的点。于是我大概就是这么维护的:

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
bool bicheck(int x, int y) { return (bool)((x == key_f) && (y == key_s)); }
void dfs4(int x, int fa) {
dep[x] = dep[fa] + 1;
if (x == loop_f) {
int t, q, p = 0, op = 0;
int cld[2] = { loop_s, loop_c };
if (cld[0] < cld[1])
t = cld[0], q = cld[1];
else
t = cld[1], q = cld[0];
dep[t] = dep[q] = dep[x] + 1;
if (t == lj[tot])
reverse(lj + 1, lj + tot + 1);
op = maxx[lj[1]];
for (int k = 2; k < tot; ++k) {
if (op <= lj[k])
op = 0;
if (lj[k] > q && lj[k] > op) {
key_s = lj[k];
key_f = lj[k - 1];
for (int j = 2; j < k; ++j) dep[lj[j]] = dep[lj[j - 1]] + 1;
for (int j = tot - 1; j >= k; --j) dep[lj[j]] = dep[lj[j + 1]] + 1;
break;
}
op = max(maxx[lj[k]], op);
}
if (!key_s) {
for (int j = 2; j < tot; ++j) dep[lj[j]] = dep[lj[j - 1]] + 1;
}
}
}

然而…这还是错的。因为如果上面存在某个外向枝内的点 $x$ 比当前点编号要小,但是在当时并不应该提前走 $x$,那么此时如果走下去,$x$ 就会比当前点的时间戳要靠后,不如直接走 $x$ 。就比如下面这张图,应该断掉 $(3,5)$ ,先走 $5$ 再回溯到 $4$ 显然不如直接走 $4$ 更优。

于是冷静了一下改成用 set 去维护 lower_bound 和当前最小值:

1
2
3
4
5
6
7
8
9
10
11
12
stt.insert(maxx[lj[1]]);
for (int k = 2; k < tot; ++k) {
while ((!stt.empty()) && (*stt.begin() <= x)) stt.erase(stt.begin());
if (lj[k] > q && (stt.empty() || stt.lower_bound(lj[k]) != stt.begin())) {
key_s = lj[k];
key_f = lj[k - 1];
for (int j = 2; j < k; ++j) dep[lj[j]] = dep[lj[j - 1]] + 1;
for (int j = tot - 1; j >= k; --j) dep[lj[j]] = dep[lj[j + 1]] + 1;
break;
}
stt.insert(maxx[lj[k]]);
}

但这样还是不对…在我冷静了很久之后发现…似乎很难确定到底该走到哪个点断掉,因为这样贪心相当于还是只想了一半期间一度陷入自闭

然后灵光一闪。发现外向枝里面可能有比当前大的点,也可能有比当前小的点。那么如果回溯时一定会先去遍历比当前点大的点就肯定不会断,如果一定会去遍历比当前小的点就一定要断。否则如果可以选择先遍历大的还是小的,就可以根据最初的那个 check 来判断到底断不断,因为此时外向枝不再有影响。于是就拿了个线段树维护了一下时间戳。然后就过掉了。

总结一下,还是自己思路太不清晰、太不仔细导致平白无故浪费了许多时间。写代码的时候不知道为什么,有一种「这样一定是对的」的诡异勇气让我无法静下心来思考…

还是实战过少。可能需要模拟赛来补救一下这块短板。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
int tot ;
int key_f ;
int key_s ;
int loop_f ;
int loop_s ;
int loop_c ;
int fr[MAXN] ;
int dep[MAXN] ;
int base[MAXN] ;
int maxx[MAXN] ;
bool vis[MAXN] ;

queue <int> q ;

void dfs3(int x, int fa){
if (vis[x]){
loop_f = x ;
loop_s = fa ;
int t = loop_s ;
while (t != loop_f)
base[++ tot] = t, t = fr[t] ;
return ;
} vis[x] = 1 ;
for (int k = head[x] ; k ; k = next(k)){
if (to(k) != fa){
maxx[x] = max(maxx[x], to(k)) ;
fr[to(k)] = x, dfs3(to(k), x) ;
}
}
}
bool bicheck(int x, int y){
return (bool)((x == key_f) && (y == key_s)) ;
}

int seg[MAXN * 3] ;
void _up(int rt){
seg[rt] = max(seg[rt << 1], seg[rt << 1 | 1]) ;
}
void upd(int rt, int l, int r, int pos, int v){
if (l == r){
seg[rt] = v ;
return ;
}
int mid = (l + r) >> 1 ;
if (pos <= mid) upd(rt << 1, l, mid, pos, v) ;
else upd(rt << 1 | 1, mid + 1, r, pos, v) ; _up(rt) ;
}
int query(int rt, int l, int r, int ql, int qr){
int mid = (l + r) >> 1, res = 0 ;
if (ql <= l && r <= qr) return seg[rt] ;
if (ql <= mid) chkmax(res, query(rt << 1, l, mid, ql, qr)) ;
if (qr > mid) chkmax(res, query(rt << 1 | 1, mid + 1, r, ql, qr)) ;
return res ;
}
void dfs4(int x, int fa){
dep[x] = dep[fa] + 1 ;
if (x == loop_f){
int t, q, p = 0 ;
int op = 0, pre = 0 ;
int cld[2] = {loop_s, loop_c} ;
if (cld[0] < cld[1])
t = cld[0], q = cld[1] ;
else t = cld[1], q = cld[0] ;
dep[t] = dep[q] = dep[x] + 1 ;
if (t == base[tot])
reverse(base + 1, base + tot + 1) ;
for (int j = head[base[1]] ; j ; j = next(j)){
if (to(j) == x) continue ;
if (to(j) <= base[2]) continue ;
upd(1, 1, n, to(j), dep[base[1]]) ;
}
for (int k = 2 ; k <= tot ; ++ k){
chkmax(pre, base[k]) ;
int more_t = query(1, 1, n, base[k] + 1, n) ;
int less_t = query(1, 1, n, 1, base[k] - 1) ;
if (less_t == more_t && pre > q) {
key_s = base[k] ;
key_f = base[k - 1] ;
for (int j = tot - 1 ; j >= k ; -- j)
dep[base[j]] = dep[base[j + 1]] + 1 ;
break ;
}
else if (less_t > more_t){
key_s = base[k] ;
key_f = base[k - 1] ;
for (int j = tot - 1 ; j >= k ; -- j)
dep[base[j]] = dep[base[j + 1]] + 1 ;
break ;
}
int y = base[k] ;
dep[base[k]] = dep[base[k - 1]] + 1 ;
for (int j = head[y] ; j ; j = next(j)){
if (to(j) == base[k - 1]) continue ;
if (to(j) <= base[k + 1]) continue ;
upd(1, 1, n, to(j), dep[y]) ;
}
}
if (!key_s){
for (int j = 2 ; j <= tot ; ++ j)
dep[base[j]] = dep[base[j - 1]] + 1 ;
}
}
for (int k = head[x] ; k ; k = next(k)){
if (to(k) == fa) continue ;
if (bicheck(x, to(k))) continue ;
if (bicheck(to(k), x)) continue ;
if (dep[to(k)] && dep[to(k)] != dep[x] + 1) continue ;
dfs4(to(k), x) ;
}
}
void dfs5(int u, int fa){
sz[u] = 1 ; //cout << u << '\n' ;
for (int k = head[u] ; k ; k = next(k))
if (to(k) != fa && !bicheck(u, to(k)) && !bicheck(to(k), u) && dep[to(k)] == dep[u] + 1)
dfs5(to(k), u), sz[u] += sz[to(k)], son[u].push_back(to(k)) ;
}
void dfs6(int u, int fa){
int j = 1, k ; o[++ res] = u ;
for (auto k : son[u]) dfs6(k, u) ;
}
int main(){
//freopen("travel.in", "r", stdin);
//freopen("travel.out", "w", stdout);
cin >> n >> m ; int i, u, v ;
memset(ans, 63, sizeof(ans)) ;
for (i = 1 ; i <= m ; ++ i)
u = qr(), v = qr(), add(u, v), ++ deg[u], ++ deg[v] ;
if (m == n - 1){}
else {
dfs3(1, 0) ; tot -- ;
swap(loop_s, loop_f) ;
if (base[1] == loop_s)
loop_c = base[tot] ;
else loop_c = base[1] ; dfs4(1, 0) ;
dfs5(1, 0) ;
for (i = 1 ; i <= n ; ++ i)
sort(son[i].begin(), son[i].end()) ;
dfs6(1, 0) ; memcpy(ans, o, sizeof(o)) ;
}
for (i = 1 ; i <= n ; ++ i)
printf("%d ", ans[i]) ; return 0 ;
}

E 填数游戏

考虑暴力的话自然是搜索…当时在考场上写了好久…幸亏最后调出来了。依稀记得最后 $30min$ 调出来这个搜索之后,找到规律之后无比兴奋…兴奋到没有打最后一题的暴力qaq

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
int Ans ; char S[20000][200], W[20000][200] ;
int N, M, T[20000], i, j, k, tot, map[250][250] ;

void dfs(int x, int y, int step){
if (x == N && y == M) {
W[tot][step] = (char)(map[N][M] + 48) ;
return ;
}
if (x == N) S[tot][step] = 'R', W[tot][step] = (char)(map[x][y] + 48), dfs(x, y + 1, step + 1) ;
else if (y == M) S[tot][step] = 'D', W[tot][step] = (char)(map[x][y] + 48), dfs(x + 1, y, step + 1) ;
else S[tot][step] = 'R', W[tot][step] = (char)(map[x][y] + 48), dfs(x, y + 1, step + 1),
strcpy(S[tot + 1], S[tot]), ++ tot, S[tot][step] = 'D', strcpy(W[tot], W[tot - 1]), W[tot][step] = (char)(map[x][y] + 48), dfs(x + 1, y, step + 1) ;
}
inline bool check(){
for (int A = 1 ; A < tot ; ++ A)
for (int B = A ; B <= tot ; ++ B){
bool flag = 0 ;
for(int di = 0 ; di < N + M - 2 ; ++ di)
if (S[A][di] > S[B][di]) { flag = 1 ; break ; }
else if (S[A][di] < S[B][di]){ flag = 0 ; break; }
for(int di = 0 ; di < N + M - 1 ; ++ di)
if ((W[A][di] > W[B][di]) && flag) return 0 ;
else if (W[A][di] < W[B][di]) break ;
}
for (int A = 1 ; A <= tot ; ++ A)
for (int B = 1 ; B < A ; ++ B){
bool flag = 0 ;
for(int di = 0 ; di < N + M - 2 ; ++ di)
if (S[A][di] < S[B][di]) { flag = 1 ; break ; }
else if (S[A][di] > S[B][di]){ flag = 0 ; break; }
for(int di = 0 ; di < N + M - 1 ; ++ di)
if (W[A][di] < W[B][di] && flag) return 0 ;
else if (W[A][di] > W[B][di]) break ;
}
return 1 ;
}
inline LL expow(LL A, LL B){
LL res = 1 ;
while (B){
if (B & 1) res = res * A % Mod ;
A = A * A % Mod, B >>= 1 ;
}
return res % Mod ;
}
int main(){
cin >> N >> M ;
if (N > M) swap(N, M) ;
if (N <= 4 && M <= 4){
int Max = (1 << N * M) - 1 ;
for (i = 0 ; i <= Max ; ++ i){
tot = 0 ;
for (j = 1 ; j <= N ; ++ j)
for (k = 1 ; k <= M ; ++ k)
map[j][k] = (1 << tot & i) ? 1 : 0, ++ tot ;
tot = 1, dfs(1, 1, 0) ;
if (check()) ++ Ans ;
}
cout << Ans << endl ;
}
else if (N == 2){
cout << 12 * expow(3, M - 2) % Mod << endl ;
}
else if (N == 3){
cout << 112 * expow(3, M - 3) % Mod << endl ;
}
else if (N == 5 && M == 5) cout << 7136 << endl ;
else if (N == 5 && M == 4) cout << 2688 << endl ;
return 0 ;
}

算了一下这个搜索的复杂度。发现大概是什么 $O\left(2^{m\times n}\cdot \binom{n+m-2}{n-1}^2\right)$ 的,这东西在 $n=5,m=5$ 的时候计算量是 $164416716800\approx1.64\cdot 10^{11}$。不过打出 $n=3,m=4/5/6$ 的表来还是戳戳有余的($n=3,m=6,T=115605504$)。

然后就又是喜闻乐见的找性质环节:

1、不难归纳出来,反对角线(即 $n+m$ 为定值)上所有的位置,按照列号从小到大来排布,填的数构成的数列应该不下降。具体可以考虑归纳,大概就是说如果有两个序列的一部分只有两步不同,即 ...WWWWDDDD......WWWDWDDD...,那么必然存在一个经过了 $(i,j)$ 而另一个经过了 $(i+1,j-1)$,那么就必然需要 $a_{i+1,j-1}\geq a_{i,j}$。那么一直归纳下去,不难发现这是必要条件

2、然而只考虑第一点是错的。自己还是把暴力和构造分别打了个表出来才明白哪不对…具体来说比如这个矩阵

1
2
3
1 1 1
1 1 0
1 1 1

那么 WDDWDWWD 这两个走法的关系就显然不对。然后抽象了一会儿觉得可能是要考虑对称位置,但是发现 $n\ne m$ 时并不可以良定义「对称」;又觉得可能是需要到 $i,j$ 的路径都本质不同,但是发现并不会设计状态来算这个步数…

还是知乎好!从知乎上学了一波,感觉十分深刻。大概就是考虑如果 $(i,j-1)=(i-1,j)$ ,那么以 $(i,j)$ 为左上角的所有矩阵的反对角线上的数都必须相等。感觉这个抽象十分到位。考虑如果某条对角线上的两个点 $(a_1,b_1),(a_2,b_2)$ 不同,那么必然可以让两条路线让他们在 $(c,d)$ 处分开,一个尽量 W 一个尽量 D,注意到由于 W&D 的数量是固定的,所以尽量 W 的那个一开始字典序一定偏小,那么该路径走到 $(a_2,b_2)$ 就会使答案不合法。

Sol 1

比较直接的相反就是继续爆搜。发现这样优化了一波之后复杂度变成了 $O(2^{n\times m}\cdot n^2m^2)$ 的,那么 $n=m=5$ 时的运算量就变成了 $20971520000\approx 2.1\cdot 10^{10}$ …好像也没快多少…

然后大概就是考虑对着这两个条件进行 dp。然后大概发现自己不会怎么 dp 对角线。然后选择剪枝。发现复杂度大头是 $2^{n\times m}$,考虑缩一下这个,大概就是确定每条对角线哪个位置是分界点。那么设 $n\leq m$,这样的复杂度大概是 $O\left((n!)^2\cdot n^{m-n}\cdot n^2m^2\right)$ 。稍微优化一波 checker 就可以做到 $O\left((n!)^2\cdot n^{m-n}\cdot nm\right)$ 。但这样在 $n=m=7$ 的时候大概是 $1244678400=1.24\cdot 10^9$ 依旧不是很能过然后发现(1,1)和(n,n)并不重要就可以有一个1/4的常数。但无论怎样,80 分确实是有了。算了一下 $n=m=8$ 的时候 $ T= 104044953600\approx 10^{11}$,如果按照一秒钟 $5e8$ 的速度大概是 $2000s+$ (其实不到 $2min$ 就出来了),找一波规律就 $100$ 了。

不知为何似乎有坑点。发现当 $n=6$ 的时候应该拿 $m=7$ 时算的数来算,因为此时似乎 $ans(6,7)\ne3\cdot ans(6,6)$ ?似乎 $n=8$ 时也是这样…挺奇怪的。并且 $8,9$ 至少要多一个 $81$ 倍常数…就很爆炸。不过似乎确实也在 $10min$ 之内出了结果。大力出奇迹啊。

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
int ans, vis[100][100] ;
int n, m, tot, map[100][100] ;

inline bool check(int owo){
for (int i = 2 ; i <= n ; ++ i)
for (int j = 2 ; j <= m ; ++ j){
if (vis[i][j] == owo) continue ;
if (map[i - 1][j] == map[i][j - 1]){
for (int x = i + 1 ; x <= n ; ++ x)
for (int y = j ; y < m ; ++ y)
if (map[x][y] == map[x - 1][y + 1])
vis[x][y] = owo ; else return 0 ;
}
}
return 1 ;
}
inline ll expow(ll x, ll y){
ll res = 1 ;
while (y){
if (y & 1) res = res * x % Mod ;
x = x * x % Mod, y >>= 1 ;
}
return res % Mod ;
}
void dfs(int s){
if (s == n + m - 1){
return void(ans += check(++ tot)) ;
}
if (s <= n){
for (int x, y, i = 0 ; i <= s ; ++ i){
x = s, y = 1 ;
while (x >= s - i + 1)
map[x][y] = 1, x --, y ++ ;
dfs(s + 1) ;
x = s, y = 1 ;
while (x >= s - i + 1)
map[x][y] = 0, x --, y ++ ;
}
}
else if (s <= m){
for (int x, y, i = 0 ; i <= n ; ++ i){
x = n, y = s - n + 1 ;
while (x >= n - i + 1)
map[x][y] = 1, x --, y ++ ;
dfs(s + 1) ;
x = n, y = s - n + 1 ;
while (x >= n - i + 1)
map[x][y] = 0, x --, y ++ ;
}
}
else {
int t = n - (s - m) ;
for (int x, y, j, i = 0; i <= t ; ++ i){
x = n, y = s - n + 1, j = 1 ;
while (j <= i)
map[x][y] = 1, ++ j, x --, y ++ ;
dfs(s + 1) ;
x = n, y = s - n + 1, j = 1 ;
while (j <= i)
map[x][y] = 0, ++ j, x --, y ++ ;
}
}
}
int main(){
cin >> n >> m ;
if (n > m) swap(n, m) ;
if (n + m <= 12) dfs(2), cout << 4 * ans << endl ;
else if (n == 2) cout << 12ll * expow(3, m - 2) % Mod << endl ;
else if (n == 3) cout << 112ll * expow(3, m - 3) % Mod << endl ;
else if (n == 6) cout << 170112ll * expow(3, m - 7) % Mod << endl ;
else if (n == 7) cout << 453504ll * expow(3, m - 7) % Mod << endl ;
else if (n == 8){
if (m == 8) cout << 3626752 << '\n' ;
else cout << 10879488ll * expow(3, m - 9) % Mod << endl ;
}
return 0 ;
}

Sol 2

学了一波状压对角线,感觉自己是弟弟。大概就是考虑如何把两个限制写到状态里面。发现可以设状态 $f_{i,j,s}$ 表示考虑前 $i$ 条对角线,第 $i$ 条对角线从下至少染了 $j$ 个 $1$,对角线上每个位置(以及所包含的那个矩形)是否合法(用 $s$ 表示)的方案数。转移就可以枚举上一条对角线的状态。这样最后就是 $O(2^n\cdot n\cdot n^2\cdot m)$ 的复杂度。

但显然最后答案还是要打表找规律的

F 保卫王国

给定树,求最小点覆盖。多组询问,每组询问会钦定两个点被覆盖或者不被覆盖,并询问最小边覆盖。

$1\leq n,m\leq 10^5$ 。

Sol 1 链分治维护dp

大概就是考虑最小边覆盖的 $dp$

然后考虑设 $g_{x,0}$ 表示只考虑了 $x$ 的轻儿子时的最小边覆盖。那么有

其中 $z$ 是 $x$ 的重儿子。那么不难知道转移矩阵应该写成

然后就可以直接用 LCT 维护链来做了。写的时候有不少细节需要注意…自己还是太菜了…不过 LCT 确实挺短的。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

int lans;
int n, m;
int base[N];

vint E[N];

il ll min(ll a, ll b) { return b > a ? a : b; }
struct mat {
ll m[2][2];
il ll minx() { return min(m[1][0], m[1][1]); }
il mat(ll a = Q, ll b = Q, ll c = Q, ll d = Q) {
m[0][0] = a;
m[0][1] = b;
m[1][0] = c;
m[1][1] = d;
}
il mat friend operator*(const mat &a, const mat &b) {
mat c;
c = mat(); // c.reset() ;
c.m[0][1] = min(a.m[0][0] + b.m[0][1], a.m[0][1] + b.m[1][1]);
c.m[1][1] = min(a.m[1][0] + b.m[0][1], a.m[1][1] + b.m[1][1]);
c.m[0][0] = min(a.m[0][0] + b.m[0][0], a.m[0][1] + b.m[1][0]);
c.m[1][0] = min(a.m[1][0] + b.m[0][0], a.m[1][1] + b.m[1][0]);
return c;
}
};

#define f(x) s[x].f
#define fa(x) s[x].fa
#define g_0(x) s[x].g[0]
#define g_1(x) s[x].g[1]
#define lc(x) s[x].son[0]
#define rc(x) s[x].son[1]

struct lct {
mat f;
int fa;
ll g[2];
int son[2];
} s[N * 3];

il bool w_k(int x) { return (rc(fa(x)) == x); }
il bool notroot(int x) { return (lc(fa(x)) == x || rc(fa(x)) == x); }
il void _up(int x) {
f(x) = mat(Q, g_1(x), g_0(x), g_1(x));
f(x) = f(rc(x)) * f(x) * f(lc(x));//1 转移顺序 必须要从下到上转移 即 splay 里要严格按照顺序来转移
}
il void rotate(int x) {
int da = fa(x);
int dada = fa(da);
bool w = w_k(x), ww = w_k(da);
if (notroot(da))
s[dada].son[ww] = x;
fa(x) = dada;
fa(s[x].son[w ^ 1]) = da;
s[da].son[w] = s[x].son[w ^ 1];
s[x].son[w ^ 1] = da;
fa(da) = x;
_up(da);
_up(x);
}
void splay(int x) {
while (notroot(x)) {
if (notroot(fa(x)))
rotate(w_k(fa(x)) == w_k(x) ? fa(x) : x);
rotate(x);
}
}
void access(int x) {
int y = 0;
for (; x; x = fa(y = x)) {
splay(x);
g_1(x) += f(rc(x)).minx() - f(y).minx();
g_0(x) += f(rc(x)).m[1][1] - f(y).m[1][1];
rc(x) = y;
_up(x);
}
}

void prelude(int x, int dad) {
g_0(x) = 0;
g_1(x) = base[x];
for (auto k : E[x]) {
if (k != dad) {
fa(k) = x;
prelude(k, x);
g_0(x) += g_1(k);
g_1(x) += min(g_0(k), g_1(k));
}
}
f(x) = mat(Q, g_1(x), g_0(x), g_1(x));
}

void _upd(int x, int y, ll v) {
access(x);
splay(x);
s[x].g[y ^ 1] += v;
_up(x);
}
char pks[5];
int main() {
freopen("defense.in", "r", stdin);
freopen("defense.out", "w", stdout);
qr(n), qr(m);
cin >> pks;
int x, y, a, b;
for (int i = 1; i <= n; ++i) qr(base[i]);
for (int i = 1; i < n; ++i)
qr(x), qr(y), E[x].p_b(y), E[y].p_b(x);
prelude(1, 0);
f(0) = mat(0, Q, Q, 0);
while (m--) {
qr(x);
qr(a);
_upd(x, a, Q);
qr(y);
qr(b);
_upd(y, b, Q);
splay(1);
if (f(1).minx() >= Q)
puts("-1");
else
printf("%lld\n", f(1).minx());
_upd(x, a, -Q);
_upd(y, b, -Q);
}
return 0;
}

Sol 2 倍增

大概就是说,询问之间本身都是独立的。所以如果强行上动态 dp 有点过犹不及。

于是考虑大力倍增。水平不够暂时咕咕咕了。

CSP2019

A 格雷码

就,模拟一下?我正我是分治了一波。这种题怎么做都可以吧。

做的时候似乎是特判了一波什么 1<<64long long 的东西,好像还是挺有用的?

1
2
3
4
5
6
7
8
9
10
11
void solve(ull l, ull r, ull p){
if (l + 1 == r){
if (l == p) ans[++ cnt] = 0 ;
else ans[++ cnt] = 1 ; return ;
}
ull mid = (l + r) >> 1 ;
if (p > mid) solve(l, mid, r - p) ;
else solve(l, mid, p) ;
if (p > mid) ans[++ cnt] = 1 ;
else ans[++ cnt] = 0 ;
}

B 括号树

啊这,挺水的吧。记着考场上是飞快的想出了 $O(n^2)$ 的做法,想了想可以线性,写了一会儿之后发现不会给 devc++ 开栈…就十分尴尬…然后发现如果是一条链的话是有快速写法的,就写了个等价的链做法过了大样例…然后改来改去就拍上了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int u, int ff){
int mt = 0 ; fa[u] = ff ;
if (base[u] == '(') stk[++ ctn] = u ;
else
if (ctn){
mt = stk[ctn --] ;
g[u] = g[fa[mt]] + 1 ;
}
f[u] = f[ff] + g[u] ;
for (int k = head[u] ; k ; k = next(k))
if (to(k) != ff) dfs(to(k), u) ;
if (base[u] == '(') stk[ctn --] = 0 ;
else if (mt) stk[++ ctn] = mt ;
}

C 树上的数

给定一个大小为 $n$ 的树,它共有 $n$ 个结点与 $n − 1$ 条边,结点从 $1 \sim n$ 编号。初始时每个结点上都有一个 $1 \sim n$ 的数字,且每个 $1 \sim n$ 的数字都只在恰好一个结点上出现。

接下来你需要进行恰好 $n − 1$ 次删边操作,每次操作你需要选一条未被删去的边,此时这条边所连接的两个结点上的数字将会交换,然后这条边将被删去。

$n − 1$ 次操作过后,所有的边都将被删去。此时,按数字从小到大的顺序,将数字 $1 \sim n$ 所在的结点编号依次排列,就得到一个结点编号的排列 $P_i$。现在请你求出,在最优操作方案下能得到的字典序最小的 $P_i$。

$1\leq n\leq 2\times 10^3$ 。

咕咕咕。

这种题必然是要自己想的吧。那可能要多想几天。就暂时咕咕咕了。

D Emiya 家今天的饭

给定一个矩阵,每个元素有一个固定的选择方案数 $a_{i,j}$,每一行至多选一个元素,每一列选的元素至多是选择元素总个数的一半,求总方案数。

$1 \le n \le 100$,$1 \le m \le 2000$,$0 \le a_{i,j} < 998,244,353$ 。

首先对于 $64$ 分 $2\leq m\leq 3$,可以直接暴力记一下每一行选了多少个元素,转移比较 trivial,但是有细节…就是转移的时候不要瞎 jb 判,最后统计答案的时候再判——感觉是个很浅显的结论我竟然调了 $10min+$ !

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
int dp[2][S][S][S] ;
int pd[2][S][S][S][S] ;

void solve1(){//m=2
int d = 1 ;
dp[0][0][0][0] = 1 ;
for (int i = 1 ; i <= n ; ++ i){
memset(dp[d], 0, sizeof(dp[d])) ;
for (int j = 0 ; j <= i ; ++ j){
for (int k = 0 ; k <= j ; ++ k){
add(dp[d][j][k][j - k], dp[d ^ 1][j][k][j - k]) ;
if (k)
add(dp[d][j][k][j - k], 1ll * dp[d ^ 1][j - 1][k - 1][j - k] * base[i][1] % P) ;
if (j - k)
add(dp[d][j][k][j - k], 1ll * dp[d ^ 1][j - 1][k][j - k - 1] * base[i][2] % P) ;
}
}
d ^= 1 ;
}
for (int i = 1 ; i <= n ; ++ i)
for (int j = 0 ; j <= i ; ++ j)
if ((j <= i / 2) && (i - j <= i / 2))
add(ans, dp[n & 1][i][j][i - j]) ;
cout << ans << '\n' ;
}
void solve2(){//m=3
int d = 1 ;
pd[0][0][0][0][0] = 1 ;
for (int i = 1 ; i <= n ; ++ i){
memset(pd[d], 0, sizeof(pd[d])) ;
for (int j = 0 ; j <= i ; ++ j){
for (int k = 0 ; k <= j ; ++ k){ // (j-k)+o+(k-o)=j
for (int o = 0 ; o <= k ; ++ o){
add(pd[d][j][j - k][o][k - o], pd[d ^ 1][j][j - k][o][k - o]) ;
if (j - k)
add(pd[d][j][j - k][o][k - o], 1ll * pd[d ^ 1][j - 1][j - k - 1][o][k - o] * base[i][1] % P) ;
if (o)
add(pd[d][j][j - k][o][k - o], 1ll * pd[d ^ 1][j - 1][j - k][o - 1][k - o] * base[i][2] % P) ;
if (k - o)
add(pd[d][j][j - k][o][k - o], 1ll * pd[d ^ 1][j - 1][j - k][o][k - o - 1] * base[i][3] % P) ;
}
}
}
d ^= 1 ;
}
for (int i = 2 ; i <= n ; ++ i)
for (int j = 0 ; j <= i ; ++ j)
for (int k = 0 ; k <= j ; ++ k)
if ((k <= i / 2) && ((j - k) <= i / 2) && ((i - j) <= i / 2))
add(ans, pd[n & 1][i][k][j - k][i - j]) ;
cout << ans << '\n' ;
}

然后考虑更高分做法,大概就是要想到容斥。考虑将问题转化成「总方案数-存在某一行 $>\lfloor\frac{k}{2}\rfloor$ 的方案数」,那么发现后面一项,对于某种方案,至多存在一列 $>\lfloor\frac{k}{2}\rfloor$。 所以容斥系数大概就是 $1~0~0\cdots$。那么如果设 $s_i=\sum_{j=1}^m a_{i,j}$ ,可以知道总方案数是 $\prod (s_i+1)-1$。考虑单独一行怎么算,发现只需要记一下总共选了多少个/当前行选了多少个即可。复杂度 $O(n^3m)$,可以获得 $84$ 分。

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
void solve3(){
int d ; ans = 1 ;
for (int i = 1 ; i <= n ; ++ i) sum[i][0] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= m ; ++ j)
sum[i][j] = addn(sum[i][j - 1], base[i][j]) ;
for (int i = 1 ; i <= n ; ++ i)
ans = 1ll * ans * sum[i][m] % P ; dec(ans, 1) ;
for (int j = 1 ; j <= m ; ++ j){
d = 0 ; f[0][0][0] = 1 ;
for (int i = 1 ; i <= n ; ++ i){
d ^= 1 ; int ts ;
ts = sum[i][m] - 1 ;
for (int k = 0 ; k <= n ; ++ k)
for (int o = 0 ; o <= n ; ++ o){
f[d][k][o] = f[d ^ 1][k][o] ;
if (k) add(f[d][k][o], 1ll * f[d ^ 1][k - 1][o] * (ts - base[i][j]) % P) ;
if (k && o) add(f[d][k][o], 1ll * f[d ^ 1][k - 1][o - 1] * base[i][j] % P) ;
}
}
for (int j = 1 ; j <= n ; ++ j)
for (int k = 1 ; k <= j ; ++ k)
if (j - k < k) dec(ans, f[n & 1][j][k]) ;
memset(f[0], 0, sizeof(f[0])) ;
}
cout << ans << '\n' ;
}

之后发现…本质上也同样不需要第二维。因为在钦定了某一列是最多的之后,就不再需要关心次序,只需要关心是否比其它列的总和要多就好了。所以可以维护这个差分值,相当于将状态合并了。于是最后复杂度 $O(n^2m)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve4(){
int d ; ans = 1 ;
for (int i = 1 ; i <= n ; ++ i) sum[i][0] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= m ; ++ j)
sum[i][j] = addn(sum[i][j - 1], base[i][j]) ;
for (int i = 1 ; i <= n ; ++ i)
ans = 1ll * ans * sum[i][m] % P ; dec(ans, 1) ;
for (int j = 1 ; j <= m ; ++ j){
d = 0 ; g[0][n] = 1 ;
for (int i = 1 ; i <= n ; ++ i){
d ^= 1 ;
int ts = sum[i][m] - 1 ;
memset(g[d], 0, sizeof(g[0])) ;
for (int k = 0 ; k <= n + n ; ++ k){ g[d][k] = g[d ^ 1][k] ;
if (k > 0) add(g[d][k], 1ll * g[d ^ 1][k - 1] * base[i][j] % P) ;
if (k < n + n) add(g[d][k], 1ll * g[d ^ 1][k + 1] * decn(ts, base[i][j]) % P) ;
}
}
for (int j = 1 ; j <= n ; ++ j) dec(ans, g[n & 1][n + j]) ;// , cout << g[n & 1][n + j] << '\n' ;
memset(g[0], 0, sizeof(g[0])) ;
}
cout << ans << '\n' ;
}

于是我就把全部的 subtask 都写了,加起来120行左右。

E 划分

给定一个长为 $n$ 的序列 $\{a_n\}$ 。需要找到一些分界点 $1 \le k_1 < k_2 < \cdots < k_p < n$,使得:

同时最小化

$2 \le n \le 4 \times 10^7 , 1 \le a_i \le 10^9$。

大概一个比较 trivial 的想法是记 $f_{i,v}$ 表示前 $i$ 个数分了某些段,最后一段大小为 $v$ 的 ans。这样大概是可以拿个 $24pts$?然后再高的话就是考虑 $v$ 必然只会是连续一段,所以可以设 $f_{i,j}$ 表示前 $i$ 个数分了某些段,最后一段是 $j\sim i$ 的 ans。然后这样似乎就是 $O(n^3)$ 可以拿到 $40pts$。然后发现有神秘的单调性,大概就是发现最后要最优化的是和的平方,那么肯定是段数越多越优。那么对于每一个 $i$ 的那个使得 $j\sim i$ 最优的决策一定也会让 $len=i-j+1$ 最小。这样就可以存一下每个 $i$ 的最优决策点 $minx_i$ ,就可以实现 $O(n)$ 转移了。

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
for (i = 1 ; i <= N ; ++ i) base[i] = qr(), s[i] = s[i - 1] + base[i] ;  
if (N <= 600){
memset(dp, 127, sizeof(dp)), ans = (1ll << 60) ;
for (i = 0 ; i <= N ; ++ i) dp[0][i] = 0 ;
for (i = 1 ; i <= N ; ++ i){
for (j = 1 ; j <= i ; ++ j){
LL t = (s[i] - s[i - j]) * (s[i] - s[i - j]) ;
for (k = 0 ; k <= (i - j) ; ++ k)
if (s[i] - s[i - j] >= s[i - j] - s[i - j - k])
dp[i][j] = minn(dp[i][j], dp[i - j][k] + t) ;
else break ;
}
}
for (i = 1 ; i <= N ; ++ i) ans = min(ans, dp[N][i]) ;
cout << ans << endl ;
}
else if (N <= 5000){
memset(f, 127, sizeof(f)), f[0] = 0 ;
memset(minx, 127, sizeof(minx)), minx[0] = 0 ;
for (i = 1 ; i <= N ; ++ i)
for (j = i - 1 ; j >= 0 ; -- j)
if (s[i] - s[j] >= minx[j])
minx[i] = min(s[i] - s[j], minx[i]),
f[i] = min(f[i], f[j] + (s[i] - s[j]) * (s[i] - s[j])) ;
cout << f[N] << endl ;
}

感觉这个单调性似乎可以很强的样子?大概就是发现对于每个 $i$ ,本质上只关心他最小的那一段合法后缀是多少。于是就可以拿一个单调队列来优化了。

注意单调队列插入队尾时注意转移式的变形。感性来说为了找到最小的那个合法区间,就需要按照 $s_i-s_k\geq m(k)$ ,其中 $i$ 是将来的决策,那么就需要按照 $s_k+m(k)$ 来衡量决策。

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
void out_put(L128 x){
if (!x) return ;
out_put(x / 10) ;
cout << (LL)(x % 10) ;
}

int N, T ;
int h, t ;
int q[MAXN] ;
int pre[MAXN] ;
int base[MAXP] ;

L128 ans ;
LL s[MAXN] ;
LL minx[MAXN] ;

const int M = 1 << 30 ;
LL p, l, r, b, p0 = 1 ;
LL x, y, z, b1, b2, m ;

void gene(){
s[0] = 0 ;
x = qr(), y = qr(), z = qr() ;
b1 = qr(), b2 = qr(), m = qr() ;
for (register int i = 1 ; i <= m ; ++ i){
p = qr(), l = qr(), r = qr() ;
for (register int j = p0 ; j <= p ; ++ j){
if (j == 1) b = b1 ;
else if (j == 2) b = b2 ;
else b = (x * b2 + y * b1 + z) % M, b1 = b2, b2 = b ;
s[j] = s[j - 1] + (b % (r - l + 1) + l) ;

}
p0 = p + 1 ;
}
}
int main(){
cin >> N >> T ;
int i, j, k ; h = 1 ;
if (!T){
for (i = 1 ; i <= N ; ++ i)
base[i] = qr(), s[i] = s[i - 1] + base[i] ;
}
else gene() ; j = 0 ;
q[++ t] = 0 ; minx[0] = 0 ;
for (i = 1 ; i <= N ; ++ i){
while (h <= t && s[i] - s[q[h]] >= minx[q[h]])
j = q[h ++] ; minx[i] = s[i] - s[j] ; pre[i] = j ;
while (h <= t && minx[q[t]] + s[q[t]] >= minx[i] + s[i]) q[t --] = 0 ; q[++ t] = i ;
}
while (N)
ans += (L128)minx[N] * minx[N], N = pre[N] ;
out_put(ans) ; return 0 ;
}

话说回来,去年赛场上我甚至没有把数据生成的规则看完…因为并没有时间,也并没有能力(?)去看最后一档部分分。大概是圆了一个未竟的梦吧。

F 树的重心

小简单正在学习离散数学,今天的内容是图论基础,在课上他做了如下两条笔记:

  1. 一个大小为 $n$ 的树由 $n$ 个结点与 $n − 1$ 条无向边构成,且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边,树将分裂为若干个子树;而在树中删去一条边(保留关联结点,下同),树将分裂为恰好两个子树。
  2. 对于一个大小为 $n$ 的树与任意一个树中结点 $c$,称 $c$ 是该树的重心当且仅当在树中删去 $c$ 及与它关联的边后,分裂出的所有子树的大小均不超过 $\lfloor \frac{n}{2} \rfloor$(其中 $\lfloor x \rfloor$ 是下取整函数)。对于包含至少一个结点的树,它的重心只可能有 $1$ 或 $2$ 个。

课后老师给出了一个大小为 $n$ 的树 $S$,树中结点从 $1 \sim n$ 编号。小简单的课后作业是求出 $S$ 单独删去每条边后,分裂出的两个子树的重心编号和之和。即:

上式中,$E$ 表示树 $S$ 的边集,$(u, v)$ 表示一条连接 $u$ 号点和 $v$ 号点的边。$S’_u$ 与 $S’_v$ 分别表示树 $S$ 删去边 $(u, v)$ 后,$u$ 号点与 $v$ 号点所在的被分裂出的子树,$c(S)$ 表示树 $S$ 重心的集合。

$1\leq n\leq 3\times 10^5$ 。

Sol 1

首先考虑部分分做法?$40pts$ 就是暴力枚举切哪一条边。$55pts$ 的链在瞎映射一通可以 $O(1)$ 求出割完之后两棵树的重心分别是谁。$75pts$ 的满二叉树大概是要先找出 $\deg_x=2$ 的 $x$ ,不难知道这个一定是根,找一波规律可以发现割掉每一条边之后,较小的那一半的重心必然是这个小连通块的根,较大的那部分的重心是对面的另一个儿子,也可能是原树的根。算一下就好了。

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
91
92
93
94
95
96
97
98
99
100
101
102
103

LL ans ;
int max_dep ;
struct Edge{
int to, next ;
}E[N << 1] ;
int dep[N] ;
int deg[N] ;
int rev[N] ;
int q[5], p[5], bg, rt ;
int head[N], cnt, f[N] ;
int T, n, sz[N], e[N << 1][2] ;


void add(int u, int v){
E[++ cnt].to = v, next(cnt) = head[u], head[u] = cnt ;
E[++ cnt].to = u, next(cnt) = head[v], head[v] = cnt ;
}

void dfs1(int u, int fa){
sz[u] = 1 ;
for (int k = head[u] ; k ; k = next(k))
if (to(k) == fa) continue ; else dfs1(to(k), u), sz[u] += sz[to(k)] ;
}
void dfs(int u, int fa){
int mx = 0 ;
for (int k = head[u] ; k ; k = next(k))
if (to(k) != fa) chkmax(mx, sz[to(k)]), dfs(to(k), u) ;
chkmax(mx, sz[rt] - sz[u]) ; f[u] = mx ;
if (f[q[1]] > f[u]) q[1] = u ;
else if (f[q[2]] > f[u]) q[2] = u ;
}
void dfs2(int x, int fa){
dep[x] = dep[fa] + 1 ;
if (dep[x] > max_dep)
max_dep = dep[x], rt = x ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa) dfs2(to(k), x) ;
}
void redfs(int x, int fa){
dep[x] = dep[fa] + 1 ; rev[dep[x]] = x ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa) redfs(to(k), x) ;
}
void dfs3(int x, int fa){
dep[x] = dep[fa] + 1 ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa) dfs3(to(k), x), ans += to(k) ;
}
int main(){
// freopen("centroid12.in", "r", stdin) ;
// freopen("centroid.out", "w", stdout) ;
cin >> T ; int i, j, k ;
while (T --){
cin >> n, cnt = ans = 0 ;
memset(head, 0, sizeof(head)) ;
if (n <= 5000){
for (i = 1 ; i < n ; ++ i)
scanf("%d%d", &j, &k),
add(j, k), e[i][0] = j, e[i][1] = k ;
for (i = 1 ; i < n ; ++ i){
f[0] = n + 1 ;
q[1] = q[2] = 0,
dfs1(rt = e[i][0], e[i][1]) ;
dfs(e[i][0], e[i][1]) ;
ans += (f[q[2]] == f[q[1]]) ? (q[1] + q[2]) : q[1] ;
memset(f, 0, sizeof(f)) ;
f[0] = n + 1 ;
q[1] = q[2] = 0 ;
dfs1(rt = e[i][1], e[i][0]) ;
dfs(e[i][1], e[i][0]) ;
ans += (f[q[2]] == f[q[1]]) ? (q[1] + q[2]) : q[1] ;
}
cout << ans << endl ;
}
else if (n == 49991){
max_dep = 0 ;
for (i = 1 ; i < n ; ++ i)
scanf("%d%d", &j, &k), add(j, k) ;
dfs2(1, 0) ; redfs(rt, dep[0] = 0) ;
for (int i = 1 ; i < n ; ++ i){
if (i & 1) ans += rev[i / 2 + 1] ;
else ans += rev[i / 2] + rev[i / 2 + 1] ;
if ((n - i) & 1) ans += rev[i + (n - i) / 2 + 1] ;
else ans += rev[i + (n - i) / 2] + rev[i + (n - i) / 2 + 1] ;
}
cout << ans << '\n' ;
}
else if (n == 262143){
for (i = 1 ; i < n ; ++ i) deg[i] = 0 ;
for (i = 1 ; i < n ; ++ i){
scanf("%d%d", &j, &k) ;
add(j, k), ++ deg[j], ++ deg[k] ;
}
for (int i = 1 ; i <= n ; ++ i)
if (deg[i] == 2) { rt = i ; break ; }
dfs3(rt, 0) ; ans += 1ll * rt * (n / 2ll + 1) ; //cout << ans << '\n' ;
for (int k = head[rt] ; k ; k = next(k))
ans += 1ll * to(k) * (n - 1) / 2 ;
cout << ans << '\n' ;
}
}
}

然后考虑满分怎么做。以下设 $x$ 为当前点,$y_k$ 为 $x$ 的第 $k$ 个孩子(顺序随便定的),$z$ 为 $x$ 的重儿子,设 $s$ 为割下来的连通块大小。

这个满分做法,我自己推的比较烦,不如其他人简洁。大概就是计算每个点当重心的次数。然后我分成了三部分算。对于一个点 $x$ ,他可能成为重心,当且仅当:

Case 1 它子树内的某个子树被割了,它成为了重心

考虑此时这个小子树的子树大小需要满足什么条件。首先由于要分子树讨论,不妨设从 $y_k$ 中割掉了一棵小子树。那么考虑要满足这么几个限制:

其中 $g_y$ 为除去子树 $y$ 后剩下的子树最大值。因为根据定义本质上并不关心那些较小的子树。

于是这部分就可以分子树查。发现本质上转化成了在 $dfs$ 序上求「区间 $[l,r]$ 内值域在 $[a,b]$ 内的数有多少」,可以直接上主席树。然后这部分就做完了。

Case 2 它子树外的某个子树被割了,它成为了重心

此时还是不变,但是约束变为了

这部分也是可以直接主席树来求。但是注意解出来的 $[l,r]$ 内可能会包含从 $x$ 到根路径上点(祖先)的子树信息,可以对进退栈顺序开一棵线段树来容斥掉这一部分。

Case 3 它子树外某个不是子树的连通块被割了,它成为了重心

考虑此时割掉的一定是 $x$ 到根路径上的一条边。发现本质上依旧是

于是还是维护一棵退栈顺序的线段树来维护这个。

然后以上的线段树可以换成树状数组。于是代码:

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
int _bit[N] ;

#define low(x) (x & -x)

il void mdf(int p, int x){
for ( ; p <= n ; p += low(p)) _bit[p] += x ;
}
il int ask(int p){
int ret = 0 ;
for ( ; p ; p -= low(p)) ret += _bit[p] ;
return ret ;
}
il int qry(int l, int r){ return ask(r) - ask(l - 1) ; }
void dfs5(int x, int fa){
int l = max(1, n - 2 * sz[x]), s ;
int r = n - 2 * sz[mson[x]], k, y, g ;
if (r >= l){//Case 2
res[x] += query(_rt[0], _rt[dfn[x] - 1], 1, n, l, r) ;
res[x] += query(_rt[dfn[x] + sz[x] - 1], _rt[n], 1, n, l, r) ;
res[x] -= qry(l, r) ;
}
pre[0] = 0 ; s = edg[x].size() ; suf[s] = 0 ;
for (k = 0 ; k < s ; ++ k){
y = edg[x][k] ;
if (y == fa){ pre[k] = pre[max(0, k - 1)] ; continue ; }
pre[k] = max(pre[max(k - 1, 0)], sz[y]) ;
}
for (k = s - 1 ; ~k ; -- k){
y = edg[x][k] ;
if (y == fa){ suf[k] = suf[k + 1] ; continue ; }
suf[k] = max(suf[k + 1], sz[y]) ;
}
for (k = 0 ; k < s ; ++ k){ //Case 1
y = edg[x][k] ;
if (y == fa) continue ;
g = max(n - sz[x], suf[k + 1]) ;
if (k > 0) g = max(pre[k - 1], g) ;
l = max(1, 2 * sz[y] - n), r = n - 2 * g ;
if (r >= l)
res[x] += query(_rt[dfn[y] - 1], _rt[dfn[y] + sz[y] - 1], 1, n, l, r) ;
}
mdf(sz[x], 1) ;
for (auto k : edg[x])
if (k != fa) dfs5(k, x) ;
mdf(sz[x], -1) ;
}
void dfs6(int x, int fa, int qwq){//Case 3
int t = sz[x] + qwq ;
int r = n - 2 * sz[mson[x]] ;
int l = max(1, n - 2 * sz[x]) ;
if (r >= l)
res[x] += qry(l, r) ;
for (auto k : edg[x]){
if (k == fa) continue ;
mdf(t - sz[k], 1) ;
dfs6(k, x, t - sz[k]) ;
mdf(t - sz[k], -1) ;
}
}
int main(){
// freopen("centroid.in", "r", stdin) ;
// freopen("centroid.out", "w", stdout) ;
qr(T) ; int i, j, k ;
while (T --){
qr(n), ans = tot = 0 ;
for (i = 1 ; i <= n ; ++ i)
edg[i].clear(), mson[i] = res[i] = _bit[i] = 0 ;
for (i = 1 ; i < n ; ++ i)
qr(j), qr(k), edg[j].p_b(k), edg[k].p_b(j) ;
dfs4(1, Id = 0) ; build(_rt[0], 1, n) ;
for (i = 1 ; i <= n ; ++ i)
upd(_rt[i], _rt[i - 1], 1, n, sz[rev[i]]) ;
dfs5(1, 0) ; fill(_bit + 1, _bit + n + 1, 0) ; dfs6(1, 0, 0) ;
for (int i = 1 ; i <= n ; ++ i) ans += 1ll * res[i] * i ; qw(ans, '\n') ;
}
}

然后就做完了。复杂度是 $O(n\log n)$,但就是常数巨大…不知道为什么…感觉应该挺快才对啊(

Sol 2

草,了解完倍增做法后发现上面的主席树是真的真的无脑。

大概就是考虑一个我没发现的性质,发现对于每个点 $u$,每次重心要么是 $u$,要么就是 $u$ 的父亲以外,要么就只会是 $u$ 子树内某个点的重儿子。所以就可以倍增预处理处每个点开始 $2^i$ 个重儿子是谁。然后考虑断 $(x,y)$ 这条边之后,$y$ 就可以通过倍增的方式找到深度最大的那个重心,然后判断一下它的父亲即可;$x$ 还需要合并父亲的重心,算点边界之类的,也不是很难。

最后放一下主席树的代码,用的 ouuan 的 IO。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>

#define MAXP 5010
#define LL long long
#define to(k) E[k].to
#define next(k) E[k].next

#define p_b push_back

#define il inline

#define N 500010

using namespace std ;

template <typename T>
il void chkmin(T &x, T y){ x = x > y ? y : x ; }
template <typename T>
il void chkmax(T &x, T y){ x = x < y ? y : x ; }

template <typename T>

void debug(T *const tp, int minn, int maxn, char v = ' ', char c = '\n'){
for (int i = minn ; i <= maxn ; ++ i) cout << tp[i] << v ; cout << c ;
}

LL ans ;
int max_dep ;
struct Edge{
int to, next ;
}E[N << 1] ;
int dep[N] ;
int deg[N] ;
int dfn[N] ;
int rev[N] ;
int mson[N] ;
int q[5], p[5] ;
int bg, rt, Id ;
int head[N], cnt, f[N] ;
int T, n, sz[N], e[N << 1][2] ;

struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
inline char gc() {
#if DEBUG
return getchar();
#endif
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
return p1 == p2 ? ' ' : *p1++;
}
inline bool blank(char ch) {
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
template <class T>
inline void read(T &x) {
register double tmp = 1;
register bool sign = 0;
x = 0;
register char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
if (ch == '.')
for (ch = gc(); isdigit(ch); ch = gc())
tmp /= 10.0, x += tmp * (ch - '0');
if (sign) x = -x;
}
inline void read(char *s) {
register char ch = gc();
for (; blank(ch); ch = gc())
;
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
}
inline void read(char &c) {
for (c = gc(); blank(c); c = gc())
;
}
inline void push(const char &c) {
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <class T>
inline void write(T x) {
if (x < 0) x = -x, push('-');
static T sta[35];
T top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}
template <class T>
inline void write(T x, char lastChar) {
write(x), push(lastChar);
}
} io;

il void add(int u, int v){
E[++ cnt].to = v, next(cnt) = head[u], head[u] = cnt ;
E[++ cnt].to = u, next(cnt) = head[v], head[v] = cnt ;
}

void dfs1(int u, int fa){
sz[u] = 1 ;
for (int k = head[u] ; k ; k = next(k))
if (to(k) == fa) continue ; else dfs1(to(k), u), sz[u] += sz[to(k)] ;
}
void dfs(int u, int fa){
int mx = 0 ;
for (int k = head[u] ; k ; k = next(k))
if (to(k) != fa) chkmax(mx, sz[to(k)]), dfs(to(k), u) ;
chkmax(mx, sz[rt] - sz[u]) ; f[u] = mx ;
if (f[q[1]] > f[u]) q[1] = u ;
else if (f[q[2]] > f[u]) q[2] = u ;
}
void dfs2(int x, int fa){
dep[x] = dep[fa] + 1 ;
if (dep[x] > max_dep)
max_dep = dep[x], rt = x ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa) dfs2(to(k), x) ;
}
void redfs(int x, int fa){
dep[x] = dep[fa] + 1 ; rev[dep[x]] = x ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa) redfs(to(k), x) ;
}
void dfs3(int x, int fa){
dep[x] = dep[fa] + 1 ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa) dfs3(to(k), x), ans += to(k) ;
}

int tot ;
int sum[N * 18] ;
int _rt[N * 18] ;
int _lc[N * 18] ;
int _rc[N * 18] ;
vector <int> edg[N] ;

void dfs4(int x, int fa){
rev[dfn[x] = ++ Id] = x ;
dep[x] = dep[fa] + (sz[x] = 1) ;
for (auto k : edg[x]){
if (k != fa){
dfs4(k, x) ; sz[x] += sz[k] ;
if (sz[k] > sz[mson[x]] || !mson[x]) mson[x] = k ;
}
}
}
void build(int &rt, int l, int r){
sum[rt = ++ tot] = 0 ;
if (l == r) return void() ;
int mid = (l + r) >> 1 ;
build(_lc[rt], l, mid) ;
build(_rc[rt], mid + 1, r) ;
}
void upd(int &rt, int lst, int l, int r, int p){
rt = ++ tot ;
_lc[rt] = _lc[lst] ;
_rc[rt] = _rc[lst] ;
if (l == r)
return void(sum[rt] = sum[lst] + 1) ;
int mid = (l + r) >> 1 ;
if (p <= mid)
upd(_lc[rt], _lc[lst], l, mid, p) ;
else upd(_rc[rt], _rc[lst], mid + 1, r, p) ;
sum[rt] = sum[_lc[rt]] + sum[_rc[rt]] ;
}
int query(int u, int v, int l, int r, int ql, int qr){
int mid = (l + r) >> 1, res = 0 ;
if (ql <= l && r <= qr) return sum[v] - sum[u] ;
if (ql <= mid) res += query(_lc[u], _lc[v], l, mid, ql, qr) ;
if (qr > mid) res += query(_rc[u], _rc[v], mid + 1, r, ql, qr) ;
return res ;
}
int pre[N] ;
int suf[N] ;
int res[N] ;

int _bit[N] ;

#define low(x) (x & -x)

void mdf(int p, int x){
for ( ; p <= n ; p += low(p)) _bit[p] += x ;
}
int ask(int p){
int ret = 0 ;
for ( ; p ; p -= low(p)) ret += _bit[p] ;
return ret ;
}
int qry(int l, int r){
return ask(r) - ask(l - 1) ;
}
/*
int seg[N * 3] ;
void _up(int rt){
seg[rt] = seg[rt << 1] + seg[rt << 1 | 1] ;
}
void mdf(int rt, int l, int r, int pos, int v){
if (l == r){ seg[rt] += v ; return ; }
int mid = (l + r) >> 1 ;
if (pos <= mid) mdf(rt << 1, l, mid, pos, v) ;
else mdf(rt << 1 | 1, mid + 1, r, pos, v) ; _up(rt) ;
}
int qry(int rt, int l, int r, int ql, int qr){
int mid = (l + r) >> 1, res = 0 ;
if (ql <= l && r <= qr) return seg[rt] ;
if (ql <= mid) res += qry(rt << 1, l, mid, ql, qr) ;
if (qr > mid) res += qry(rt << 1 | 1, mid + 1, r, ql, qr) ;
return res ;
}*/
void dfs5(int x, int fa){
//int g[3] = {0, 0, 0} ;
/*for (int i = 1 ; i <= 5 ; ++ i){
// cout << x << " " ;
}puts("") ;*/
int l = max(1, n - 2 * sz[x]), s ;
int r = n - 2 * sz[mson[x]], k, y, g ;
// cout << l << " " << r << " \n" ;
if (r >= l && l > 0 && r > 0){
// cout << dfn[x] << " \n" ;
// cout << query(_rt[dfn[x] + sz[x] - 1], _rt[n], 1, n, l, r) << "#\n" ;
// cout << query(_rt[0], _rt[dfn[x] - 1], 1, n, l, r) << "#\n" ;
res[x] += query(_rt[0], _rt[dfn[x] - 1], 1, n, l, r) ;
res[x] += query(_rt[dfn[x] + sz[x] - 1], _rt[n], 1, n, l, r) ;
res[x] -= qry(l, r) ;
}
// cout << " !!!" << x << "!!! " << res[x] << '\n' ;
pre[0] = 0 ; s = edg[x].size() ; suf[s] = 0 ;
for (k = 0 ; k < s ; ++ k){
y = edg[x][k] ;
if (y == fa){ pre[k] = pre[max(0, k - 1)] ; continue ; }
pre[k] = max(pre[max(k - 1, 0)], sz[y]) ;
}
for (k = s - 1 ; ~k ; -- k){
y = edg[x][k] ;
if (y == fa){ suf[k] = suf[k + 1] ; continue ; }
suf[k] = max(suf[k + 1], sz[y]) ;
}
for (k = 0 ; k < s ; ++ k){
y = edg[x][k] ;
if (y == fa) continue ;
g = max(n - sz[x], suf[k + 1]) ;
if (k > 0) g = max(pre[k - 1], g) ;
int l = max(1, 2 * sz[y] - n), r = n - 2 * g ;
// cout << g << " " << y << " " << l << " " << r << '\n' ;
if (r >= l)
res[x] += query(_rt[dfn[y] - 1], _rt[dfn[y] + sz[y] - 1], 1, n, l, r) ;
}
/*
for (k = 0 ; k < s ; ++ k){
y = edg[x][k] ;
if (y == fa || y != mson[x]) continue ;
g[2] = suf[k + 1] ; if (k) g[2] = max(pre[k - 1], g[2]) ; break ;
}
g[0] = sz[mson[x]] ; g[1] = n - sz[x] ;
sort(g, g + 3) ;
l = max(1, 2 * g[2] - n) ;
r = min(n - g[1] * 2, 2 * sz[x] - n) ;
cout << g[2] << " " << g[1] << " " << g[0] << " $%$ \n" ;
cout << l << " " << r << " " << x << " " << res[x] << "*&*\n" ;
if (l <= r)
res[x] += query(_rt[dfn[x]], _rt[dfn[x] + sz[x] - 1], 1, n, l, r) ;
cout << x << " " << res[x] << '\n' ;*/
mdf(sz[x], 1) ;
for (auto k : edg[x]) if (k != fa) dfs5(k, x) ;
mdf(sz[x], -1) ;
}
void dfs6(int x, int fa, int qwq){
// cout << x << " " << qwq << '\n' ;
int t = sz[x] + qwq ;
int r = n - 2 * sz[mson[x]] ;
int l = max(1, n - 2 * sz[x]) ;
// cout << l << " " << r << " &\n" ;
if (r >= l)
res[x] += qry(l, r) ;
for (auto k : edg[x]){
if (k == fa) continue ;
mdf(t - sz[k], 1) ;
dfs6(k, x, t - sz[k]) ;
mdf(t - sz[k], -1) ;
}
}
int main(){
// freopen("centroid12.in", "r", stdin) ;
// freopen("centroid.out", "w", stdout) ;

io.read(T) ; int i, j, k ;
while (T --){
io.read(n), cnt = ans = 0 ;
memset(head, 0, sizeof(head)) ;
if (n <= 5000){
for (i = 1 ; i < n ; ++ i)
io.read(j), io.read(k),
add(j, k), e[i][0] = j, e[i][1] = k ;
for (int i = 1 ; i <= n ; ++ i) res[i] = 0 ;
for (i = 1 ; i < n ; ++ i){
f[0] = n + 1 ;
q[1] = q[2] = 0,
dfs1(rt = e[i][0], e[i][1]) ;
dfs(e[i][0], e[i][1]) ;
(f[q[2]] == f[q[1]]) ? (res[q[1]]++, res[q[2]] ++) : res[q[1]] ++ ;
memset(f, 0, sizeof(f)) ;
f[0] = n + 1 ;
q[1] = q[2] = 0 ;
dfs1(rt = e[i][1], e[i][0]) ;
dfs(e[i][1], e[i][0]) ;
(f[q[2]] == f[q[1]]) ? (res[q[1]]++, res[q[2]] ++) : res[q[1]] ++ ;
}
for (int i = 1 ; i <= n ; ++ i)
ans += 1ll * res[i] * i ;
cout << ans << '\n' ;
}
else if (n == 49991){
max_dep = 0 ;
for (i = 1 ; i < n ; ++ i)
io.read(j), io.read(k), add(j, k) ;
dfs2(1, 0) ; redfs(rt, dep[0] = 0) ;
for (int i = 1 ; i < n ; ++ i){
if (i & 1) ans += rev[i / 2 + 1] ;
else ans += rev[i / 2] + rev[i / 2 + 1] ;
if ((n - i) & 1) ans += rev[i + (n - i) / 2 + 1] ;
else ans += rev[i + (n - i) / 2] + rev[i + (n - i) / 2 + 1] ;
}
cout << ans << '\n' ;
}
else if (n == 262143){
for (i = 1 ; i < n ; ++ i) deg[i] = 0 ;
for (i = 1 ; i < n ; ++ i){
io.read(j), io.read(k) ;
add(j, k), ++ deg[j], ++ deg[k] ;
}
for (int i = 1 ; i <= n ; ++ i)
if (deg[i] == 2) { rt = i ; break ; }
dfs3(rt, 0) ; ans += 1ll * rt * (n / 2ll + 1) ; //cout << ans << '\n' ;
for (int k = head[rt] ; k ; k = next(k))
ans += 1ll * to(k) * (n - 1) / 2 ;
cout << ans << '\n' ;
}
else {
Id = 0 ; tot = 0 ;
memset(_rt, 0, sizeof(_rt)) ;
memset(_bit, 0, sizeof(_bit)) ;
for (i = 1 ; i <= n ; ++ i)
edg[i].clear(), mson[i] = res[i] = 0 ;
for (i = 1 ; i < n ; ++ i){
io.read(j), io.read(k) ;
edg[j].p_b(k), edg[k].p_b(j) ;
}
dfs4(1, 0) ;
build(_rt[0], 1, n) ;
for (i = 1 ; i <= n ; ++ i)
upd(_rt[i], _rt[i - 1], 1, n, sz[rev[i]]) ;
dfs5(1, 0) ;
memset(_bit, 0, sizeof(_bit)) ;
dfs6(1, 0, 0) ;
for (int i = 1 ; i <= n ; ++ i)
ans += 1ll * res[i] * i ;
cout << ans << '\n' ;
}
}
}