模板

开个坑写一下一些模板

长链剖分

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
#include <bits/stdc++.h>

#define pb emplace_back

using namespace std;
typedef long long LL;

const int maxn = 1e6 + 5;
const int INF = 1e9 + 7;

LL *now;
LL *F[maxn];
LL buf[maxn << 1];


int n;
vector<int> E[maxn];
int A[maxn], mi[maxn][21];
int son[maxn], dep[maxn], mx[maxn];
int lg[maxn];

template<typename T>
void read(T &x)
{
x = 0;
int fl = 1;
char ch = getchar();
while(!isdigit(ch) && ch != '-')
ch = getchar();
if(ch == '-')
fl = -1, ch = getchar();
while(isdigit(ch))
x = x * 10 + ch - '0', ch = getchar();
x *= fl;
}

void dfs1(int x, int fr)
{
for(auto &v : E[x]){
if(v == fr)
continue;
dep[v] = dep[x] + 1;
dfs1(v, x);
if(mx[v] > mx[son[x]])
son[x] = v;
mx[x] = max(mx[x], mx[v]);
}
mx[x] += 1;
}

int ask(int l, int r)
{
int t = lg[r - l + 1];
return min(mi[l][t], mi[r - (1 << t) + 1][t]);
}

void dp(int x, int fr)
{
F[x][0] = A[0];
if(son[x]){
F[son[x]] = F[x] + 1;
dp(son[x], x);
}

int _mx = 0;
for(auto &v : E[x]){
if(v == fr || v == son[x])
continue;
F[v] = now;
now += mx[v];
_mx = max(_mx, mx[v] + 1);
dp(v, x);
for(int j = 0; j < mx[v]; ++j){
F[x][j + 1] += F[v][j];
}

}
for(int j = 0; j <= _mx; ++j)
F[x][j] = min(F[x][j], 1LL * ask(j, dep[x] + j));
}

int main()
{
int T;
read(T);
while(T--){
read(n);
for(int i = 0; i <= now - buf; ++i)
buf[i] = 0;
for(int i = 2; i <= n; ++i)
lg[i] = lg[i >> 1] + 1;
for(int i = 1; i <= n; ++i)
E[i].clear(), son[i] = dep[i] = mx[i] = 0;
for(int i = 0; i <= n - 1; ++i){
read(A[i]);
mi[i][0] = A[i];
}

for(int j = 1; j <= lg[n]; ++j)
for(int i = 0; i + (1 << j) - 1 <= n - 1; ++i)
mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);

for(int i = 1; i <= n - 1; ++i){
int u, v;
read(u), read(v);
E[u].pb(v), E[v].pb(u);
}

dfs1(1, 0);


now = buf;
F[1] = now;
now += mx[1];
dp(1, 0);

LL ans = 0;
for(int i = 0; i < mx[1]; ++i)
ans += F[1][i];
cout << ans << endl;
}
}
  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

扫一扫,分享到微信

微信分享二维码
  • Copyrights © 2015-2024 0375w