21zr省选十连测day1
rank20,退役了退役了
A. 基础博弈练习题
考场这题玩命打表,n=8的表还是错的...得到了一个n=5的10分../xk
考虑我们转换问题,现在这类玄学毒瘤东西基本要转换成数学模型
考场上想到了类似于区间前缀后缀加减的思路,但是并不知道选择另一侧而只是选择了同一侧.....
补集转换:可行的撒谎只有1次
所以表示答案是y的话,我们的A还能能撒几次慌
那么我们会发现,B一次询问一定能够让一个前缀/后缀的数能够撒谎次数-1
就是说,询问细线
111111100|000
如果是是,那么细线前面所有数减1,他们作为答案就不能在撒谎了
而又能发现,这个竖线可以使得那些已经成为0的会变成-1,也就是说他不可能成为答案了
有了这个转换,双方的任务变成了:
Bob 要最快使得只剩下一个数非空
Alice 要控制每一次减的方向,使得bob最慢
不难发现我们每次操作的是前后缀也就是说
------00000111100000-----
是a数组唯一的形态,-几不重要
表示有i个0,后接j个1,后接k个0的还剩多少次数结束qwq
那么我们就能转移了!
case 1
case2
case3
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500;
int n, dp[MAXN][MAXN][MAXN];
inline int solve(int l, int m, int r) {
if((l == 1 && m == 0 && r == 0) || (l == 0 && m == 1 && r == 0) || (l == 0 && m == 0 && r == 1))return 0; //我知道了
if(~dp[l][m][r])return dp[l][m][r];
dp[l][m][r] = 1e9;
for(int i = 1; i <= l; ++i) {
// $$dp_{i, j, k} = min(max(dp_{i - l, j, k}, dp_{l, 0, 0}), dp_{i, j, k}), l < i$$
dp[l][m][r] = min(max(solve(l - i, m, r), solve(i + m, 0, 0)) + 1, dp[l][m][r]);
}
for(int i = 1; i <= m; ++i) {
// $$dp_{i,j,k}=min(max(dp_{l,j-l,k},dp_{i,l,j-l}),dp_{i,j,k}),l<j$$
dp[l][m][r] = min(max(solve(i, m - i, r), solve(l, i, m - i)) + 1, dp[l][m][r]);
}
for(int i = 1; i <= r; ++i) {
// $$dp_{i,j,k}=min(max(dp_{l,0,0},dp_{i,j,k-l}),dp_{i,j,k}),l<k$$
dp[l][m][r] = min(max(solve(i + m, 0, 0), solve(l, m, r - i)) + 1, dp[l][m][r]);
}
// printf("%d %d %d %d\n", l, m, r, dp[l][m][r]);
return dp[l][m][r];
}
int main() {
scanf("%d", &n);
memset(dp, -1, sizeof(dp));
solve(0, n, 0);
for(int i = 0; i < n; ++i) {
printf("%d ", solve(i, n - i, 0));
}
// for(int i = 0; i <= n; ++i) {
// for(int j = 0; j <= n; ++j) {
// for(int k = 0; k <= n; ++k) {
// if(~dp[i][j][k]) {
// printf("%d %d %d %d\n", i, j, k, dp[i][j][k]);
// }
// }
// }
// }
// printf("%d\n", dp[0][n][0]);
return 0;
}
根据邓老师所说,这个东西有决策单调性,就是固定前两维,第三维单调递增则决策点也单调递增qwq
然后我写了一个,挂了,没法调啊/ll
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 605;
int n;
int dp[MAXN][MAXN][MAXN], f[MAXN][MAXN][MAXN];
inline int solve(int l, int m, int r) {
if(~dp[l][m][r])return dp[l][m][r];
if((l == 0 && m == 0 && r == 0)) {
f[l][m][r] = -1;
return 1e9;
}
if((l == 1 && m == 0 && r == 0) || (l == 0 && m == 1 && r == 0) || (l == 0 && m == 0 && r == 1)) {
f[l][m][r] = -1;
return 0;
} //我知道了
dp[l][m][r] = 1e9;
f[l][m][r] = -1;
if(r)
solve(l, m, r - 1);//不要问我为什么,厂长是我阿福哥
if(!r) {
bool flg = 1;
for(int i = 1; i <= l; ++i) {
dp[l][m][r] = min(max(solve(l - i, m, r), solve(i + m, 0, 0)) + 1, dp[l][m][r]);
if(solve(l - i, m, r) <= solve(i + m, 0, 0) ) {
f[l][m][r] = -i; //变了变了!
flg = 0;
break;
}
}
if(flg)
for(int i = 1; i <= m; ++i) {
dp[l][m][r] = min(max(solve(i, m - i, r), solve(l, i, m - i)) + 1, dp[l][m][r]);
if(solve(i, m - i, r) <= solve(l, i, m - i)) {
f[l][m][r] = i + 10000;
flg = 0;
break;
}
}
if(flg)
for(int i = 1; i <= r; ++i) {
dp[l][m][r] = min(max(solve(i + m, 0, 0), solve(l, m, r - i)) + 1, dp[l][m][r]);
if(solve(i + m, 0, 0) <= solve(l, m, r - i)) {
f[l][m][r] = i;
flg = 0;
break;
}
}
if(flg)f[l][m][r] = -1;//我懒惰了
} else {
f[l][m][r] = f[l][m][r - 1];
bool flg = 1;
if(f[l][m][r] < 0) {
f[l][m][r] = -f[l][m][r];
for(int i = max(1, f[l][m][r] - 1); i <= l; ++i) {
dp[l][m][r] = min(max(solve(l - i, m, r), solve(i + m, 0, 0)) + 1, dp[l][m][r]);
if(solve(l - i, m, r) <= solve(i + m, 0, 0)) {
f[l][m][r] = -i;
flg = 0;
break;
}
}
if(flg)f[l][m][r] = 10000;
}
if(f[l][m][r] > 2000) {
f[l][m][r] %= 10000;
for(int i = max(1, f[l][m][r] - 1); i <= m; ++i) {
dp[l][m][r] = min(max(solve(i, m - i, r), solve(l, i, m - i)) + 1, dp[l][m][r]);
if(solve(i, m - i, r) <= solve(l, i, m - i)) {
f[l][m][r] = i + 10000;
flg = 0;
break;
}
}
if(flg)f[l][m][r] = 0;
}
if(flg)
for(int i = max(1, f[l][m][r] - 1); i <= r; ++i) {
dp[l][m][r] = min(max(solve(i + m, 0, 0), solve(l, m, r - i)) + 1, dp[l][m][r]);
if(solve(i + m, 0, 0) <= solve(l, m, r - i)) {
f[l][m][r] = i;
break;
}
}
if(flg)f[l][m][r] = r;
}
// printf("%d %d %d %d %d\n", l, m, r, dp[l][m][r], f[l][m][r]);
return dp[l][m][r];
}
int main() {
scanf("%d", &n);
memset(dp, -1, sizeof(dp));
solve(0, n, 0);
for(int i = 0; i < n; ++i) {
printf("%d ", solve(i, n - i, 0));
}
return 0;
}
std:
观察到值域很小,所以我们可以考虑翻转这个值域和定义域
表示用i次操作,然后序列中已经有j个0,k个1,后面能有的最多多少个0,可以确定下整个序列的答案
我们怎么转移呢?
翻转回来!
观察之前的转移式子,以其中一个为例
因为我们的Alice小姐要二者取max,而bob已经根据结论已经知道在前面比后面小的时候取得所有的最小值
也就是说,我们还是只需要看这个分界点处的答案
再到f数组,我们反义决策单调性
是我们在这个地方取到最小值恰好为k的时候,第三维最大可能就是这个w!
也就是说,如果我们找到这个分界点,因为我们这个分界点满足了这次操作能够确定的是尽可能长的第三维(再靠后就无法确定了,因为随着w变大我们分界点也变大),然后再这个分界点处转移我们的f数组就是可以的!
怎么确定分界点?表示在这个状态定义下的分界点位置是什么
也就是说,我们最优转移点是什么
- 均分case,
此时我们后面想要尽可能多的零就是
决策点位置在的最后一个0处
000011111000|00000000
因为此时先手选择左边保留,那右边都删掉之后左边显然是可以的
先手选择右边保留,那左边都删掉后多出k个1,然后一凑正好是个二分可以解决的问题
这个case就对应了最优决策点在j+k之后的情况,因为不难发现此时左右是(原定义)dp值相等的
此时我们想要尽可能多的零就要考虑考虑了,从上一个决策点向后跳,直到不再优为止
而此时决策点一定满足我们之前说的变化过程,就是先是回答大于等于优,再是回答小于优
这意味着什么呢?就是我们之前回答小于答案一定小于k次,因为大于等于的才大于等于k次,才能使得之前的决策点不是最优决策点
这就意味着,在之前砍一刀,一定能够满足前k-1刀可以解决回答小于的答案
这就告诉我们,从之前的决策点向后跳,直到前k-1刀不能够回答小于的答案,此时意味着我们达到了那个最优决策点(毫不留情的告诉你这个点左右切得到的答案是一样的/....),因为他必然要k刀了
其实这个和凸性很相关:一开始可以,一直逼近逼近直到不行qwq
那既然找到了这个决策点,我们再在这个位置切上一刀就是答案了
而这一刀的方向显然是向右的,因为之前我们一直是向左切的,直到这一刀那个max才切换到右边呢qwq
切:是指alice告诉我们大于还是小于....
都知道之后,代码就不难了
code:
//copy dmy!
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2050;
int n;
int dp[20][MAXN][MAXN];
int pr[20][MAXN][MAXN];
bool chk(int k, int i, int j, int pr) {
int f[3] = {0, 0, 0};
if(pr <= i + 1) {
f[0] = pr - 1 + j;
} else f[0] = i, f[1] = pr - i - 1, f[2] = j - f[1];
return dp[k][f[0]][f[1]] >= f[2];
}
int main() {
scanf("%d", &n);
for(int i = 0; i < 20; ++i) {
for(int j = 0; j <= n; ++j) {
for(int k = n - j; k >= 0; --k) {
dp[i][j][k] = -1e9;
if(i == 0) {//零次操作
if(j + k == 0)dp[i][j][k] = 1;//一个数
else if(j + k == 1)dp[i][j][k] = 0;//0个数
} else {
dp[i][j][k] = dp[i - 1][j][k] + (1 << (i - 1)) - k;
if(k == n - j)pr[i][j][k] = 1;
else pr[i][j][k] = pr[i][j][k + 1];// /jk
while(chk(i - 1, j, k, pr[i][j][k] + 1) && pr[i][j][k] <= j + k) {
pr[i][j][k]++;
}
if(!chk(i - 1, j, k, pr[i][j][k]))dp[i][j][k] = -1e9;
else {
int qwq = pr[i][j][k];
int f[3] = {0, 0, 0};
if(qwq <= j + 1) {
f[0] = j + 1 - qwq;
f[1] = k;
} else {
f[0] = qwq - j - 1;
f[1] = k - f[0];
}
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][f[0]][f[1]]);
}
}
// printf("%d %d %d %d\n", i, j, k, dp[i][j][k]);
}
}
}
for(int j = 0; j < n; ++j) {
for(int i = 0; i < 20; ++i) {
if(dp[i][j][n - j] >= 0) {
printf("%d ", i);
break;
}
}
}
return 0;
}
C
代码难度相当大,思维量适中
操作3
我们先发现暴力可以从左向右扫一遍进行规约,然后再从右向左扫一遍进行规约
会发现这样一定可行了,因为这个规约有传递性,如果左边的i位置可以约束到j,,k也可以,,而且k更狠
那么一定会有k约束了i,并且继续约束了i之后的j qwq
同理,右边向左边也一样
考虑怎么加速这个暴力的部分,我们发现一个区间规约之后就很优秀了,这么优秀的区间怎么忍心打破呢?,所以我们记录这些区间
现在对于一个操作3,有一车区间满足这个性质呢~~(是一个区间套)~~
于是发现,对于一个区间,只会有对产生影响,h为其高度
那么影响的范围也应该是最大的x,满足,然后把这一段区间都变成等差数列即可
为首相,公差为
为什么对呢?因为a_x一定会被改成那个值,然后又因为这是个优秀的区间,所以整体是个等差数列,所以前面都不行了都要改啊
最后我们要维护
-
区间和
-
区间赋值等差数列
-
区间加
-
区间二分,查询最大的x
线段树二分或者外层二分皆可以,时间复杂度
???好像漏了什么
没错,这些优秀的区间的势能分析
其实不会很差,因为我们只有2,3操作会使得优秀区间数至多+2,而这个+2显然是常数级别的,同时操作2一次会合并许多,复杂度是区间数*log
一开始有n个区间,也就是说,么得变化??
实现后的一些细节
我们线段树维护等差数列,公差的维护可以把每个数都变成下标公差的形式,然后首相对应的减去下标公差即可
同样的,注意到我们的序列其实满足很不错的性质,就是每次只会在优秀的序列中更改
那么我们只需要找到第一个向右/左不合法的位置即可,而这个位置存在的前提是那个
同时,我们一定有向右第一个合法的位置后面都合法这条性质,因为你想如果我们这个位置可以传递约束到j,又能传递约束到不合法的i,i,j不连续中间有合法的位置,可以推出最后一定这个区间不是优秀的,,那也就不可能只一次查找完成,也就是说优秀的区间传递性是极大的
综上,我们只需要二分这个合法位置即可
另外线段树二分在本题中是有区间限制和方向限制的的,以findleft(找最小)为例
对于有区间限制的线段树二分,如果我们要找最小的,就在可行的范围先尽可能的向左区间走
如果说目前限制正好分割了左右区间,会对于方向限制产生影响
要先看mid,p这一段是否完全合法,才能向左走,而如果没有这个限制,我们可以直接用右儿子的最小值判断能不能向左走qwq
code:
#include<bits/stdc++.h>
#define mkp(x,y) (make_pair(x,y))
#define ins insert
#define ls (k<<1)
#define rs (k<<1|1)
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
using namespace std;
const int MAXN = 4e5 + 7;
int n, m;
ll K;
int w[MAXN];
set<int> st;
struct rec {
ll sum;
ll A, B, add, cov;
int dir;
} tr[MAXN];
inline ll getV(int x, ll cov, int dir) {
return 1ll * dir * K * x + cov;
}
inline ll getV1(int x, ll cov, int dir) {
return dir * K * 1ll * x + cov + 1ll * K * x;
}
inline ll getV2(int x, ll cov, int dir) {
return dir * K * 1ll * x + cov - 1ll * K * x;
}
inline ll getsum(int l, int r, ll cov, int dir) {
return (getV(l, cov, dir) + getV(r, cov, dir)) * (r - l + 1) / 2;
}
namespace fastIO {
#define BUF_SIZE (1<<22)
char buf[BUF_SIZE], *p1 = BUF_SIZE + buf, *pend = buf + BUF_SIZE;
inline char nc() {
if(p1 == pend) {
p1 = buf;
pend = buf + fread(buf, BUF_SIZE, 1, stdin);
}
return *p1++;
}
inline int read() {
char s = nc();
int x = 0;
int f = 1;
for(; !isdigit(s); s = nc())if(s == '-')f = -1;
for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
return x * f;
}
}
using namespace fastIO;
namespace seg {
inline void calc(int k, int l, int r, ll v) {
rec &a = tr[k];
a.add += v;
a.A += v;
a.B += v;
a.sum += (r - l + 1) * v;
}
inline void pushdown(int k, int l, int r) {
rec &a = tr[k], &b = tr[ls], &c = tr[rs];
if(a.dir) {
b.dir = a.dir;
c.dir = a.dir;
b.cov = a.cov;
c.cov = a.cov;
int mid = (l + r) >> 1;
b.sum = getsum(l, mid, a.cov, a.dir);
c.sum = getsum(mid + 1, r, a.cov, a.dir);
b.A = min(getV1(l, a.cov, a.dir), getV1(mid, a.cov, a.dir));
b.B = min(getV2(l, a.cov, a.dir), getV2(mid, a.cov, a.dir));
c.A = min(getV1(mid + 1, a.cov, a.dir), getV1(r, a.cov, a.dir));
c.B = min(getV2(mid + 1, a.cov, a.dir), getV2(r, a.cov, a.dir));
b.add = 0;
c.add = 0;
a.dir = 0;//没用了,我们不调用他了
}
if(a.add) {
int mid = (l + r) >> 1;
calc(ls, l, mid, a.add);
calc(rs, mid + 1, r, a.add);
a.add = 0;
}
}//简 直 魔 鬼
inline void pushup(int k) {
tr[k].A = min(tr[ls].A, tr[rs].A);
tr[k].B = min(tr[ls].B, tr[rs].B);
tr[k].sum = tr[ls].sum + tr[rs].sum;
return;
}
inline ll qry(int k, int l, int r, int L, int R) {
if(L <= l && r <= R) {
return tr[k].sum;
}
pushdown(k, l, r);
int mid = (l + r) >> 1;
if(R <= mid)return qry(ls, l, mid, L, R);
else if(L > mid)return qry(rs, mid + 1, r, L, R);
else return qry(ls, l, mid, L, R) + qry(rs, mid + 1, r, L, R);
}
inline void mdf(int k, int l, int r, int L, int R, ll x) {
if(L <= l && r <= R) {
calc(k, l, r, x); // /cy
return;
}
int mid = (l + r) >> 1;
pushdown(k, l, r);
if(R <= mid)mdf(ls, l, mid, L, R, x);
else if(L > mid)mdf(rs, mid + 1, r, L, R, x);
else {
mdf(ls, l, mid, L, R, x);
mdf(rs, mid + 1, r, L, R, x);
}
pushup(k);
}
inline void mdf2(int k, int l, int r, int L, int R, ll cov, int dir) {
if(L <= l && r <= R) {
rec &a = tr[k];
a.dir = dir;
a.cov = cov;
a.sum = getsum(l, r, cov, dir);
a.A = min(getV1(l, a.cov, a.dir), getV1(r, a.cov, a.dir));
a.B = min(getV2(l, a.cov, a.dir), getV2(r, a.cov, a.dir));
a.add = 0;// /ll
return;
}
pushdown(k, l, r);
int mid = (l + r) >> 1;
if(R <= mid)mdf2(ls, l, mid, L, R, cov, dir);
else if(L > mid)mdf2(rs, mid + 1, r, L, R, cov, dir);
else {
mdf2(ls, l, mid, L, R, cov, dir);
mdf2(rs, mid + 1, r, L, R, cov, dir);
}
pushup(k);
}
int q;
inline void findleft(int k, int l, int r, int p, int v) {
int mid = (l + r) >> 1;
if(p < r) {
if(p > mid) {
findleft(rs, mid + 1, r, p, v); //只能向左走
if(q != mid + 1)return;
}
findleft(ls, l, mid, p, v);
return;
}
if(tr[k].A > v)return q = l, void(); //不行了
if(l == r)return ;
pushdown(k, l, r);
if(tr[rs].A > v)q = mid + 1, findleft(ls, l, mid, p, v);
else findleft(rs, mid + 1, r, p, v);
}
inline void findright(int k, int l, int r, int p, int v) {
int mid = (l + r) >> 1;
// printf("%d %d %d %d %d\n", l, mid, r, p, tr[k].B);
if(p > l) {
if(p <= mid) {
findright(ls, l, mid, p, v);
if(q != mid)return;
}
findright(rs, mid + 1, r, p, v);
return;
}
if(tr[k].B > v)return q = r, void();
if(l == r)return;
pushdown(k, l, r);
if(tr[ls].B > v)q = mid, findright(rs, mid + 1, r, p, v);
else findright(ls, l, mid, p, v);
}
inline void build(int k, int l, int r) {
if(l == r) {
tr[k].B = w[l] - K * l;
tr[k].A = w[l] + K * l;
tr[k].sum = w[l];
// printf("%d %lld %d?\n", l, tr[k].B, k);
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(k);
}
}
using namespace seg;
//这个是右端点
inline void work(int p, int l, int r) {
ll A = qry(1, 1, n, p, p);
ll B = qry(1, 1, n, p + 1, p + 1);
// printf("A :%lld B: %lld %lld\n", A, B, K);
if(abs(A - B) <= K)return;//没有关系
if(A < B) {
q = -1;
findright(1, 1, n, p + 1, A - p * K);
// printf("%d %d %d %d %lld?\n", p, q, l, r, A - p * K);
//直接惊恐
q = min(q, r);
//得到的位置是不合法的
mdf2(1, 1, n, p + 1, q, A - K * p, 1); //更改!qwq
} else {
q = -1;
findleft(1, 1, n, p, B + (p + 1) * K);
// if(q == 1e9)return;
q = max(q, l); //改多了我直接惊恐
mdf2(1, 1, n, q, p, B + K * (p + 1), -1);
}
}
inline void solve(int l, int r) {
auto fst = st.lower_bound(l);
auto lst = st.lower_bound(r);
for(auto it = fst; it != lst; ++it) {
work(*it, l, r);
// printf("L :%d R: %d nw: %d\n", l, r, *it);
}
st.erase(fst, lst);
if(l > 1)st.ins(l - 1);
if(r < n)st.ins(r);
return;
}
inline void solve2(int l, int r, int c) {
mdf(1, 1, n, l, r, c);
if(l > 1)st.ins(l - 1);
if(r < n)st.ins(r);
return ;
}
inline void init() {
for(int i = 1; i <= n; ++i)st.ins(i);
build(1, 1, n);
}
int main() {
n = read();
m = read();
K = read();
for(int i = 1; i <= n; ++i) {
w[i] = read();
}
init();
for(int i = 1, op, l, r, c; i <= m; ++i) {
op = read();
l = read();
r = read();
if(op == 1) {
printf("%lld\n", qry(1, 1, n, l, r));
}
if(op == 2) {
c = read();
solve2(l, r, c);
}
if(op == 3) {
solve(l, r);
}
}
return 0;
}
/*
5 5 1
5 1 3 4 2
3 3 5
2 3 5 2
1 2 3
3 4 5
1 1 3
*/
B
又是点分治
首先考虑暴力怎么实现,观察到我们最后停到哪里一定不会走回头路,因为走了回头路还不如在某一步停一下再走更优秀
同时我们也不会先停再走,假设他停了又走,对于边从u到v,那么只会使得那些u一侧的怪物更接近他,而v一侧的怪物无论接不接近都会遇上他,所以先停下再走也不行
一定是走到一个点然后驻留一辈子,所以我们可以枚举每个u作为停留点
然后这个贡献怎么办?v的贡献是:
这个就相当于,我们最后出发的dis个怪物他完蛋了,然后又因为我们是在第一个回合出现,所以下取整会少算一次(第一次)加上去,而如果正好是在这个点本身,可能又会多算一次(正好是倍数的时候),再角去
50有了,这种类似于树上深度的,启示我们使用点分治解决
链:
后i+1个点的贡献已经算出,怎么推得i号点的贡献呢?
考虑观察这个式子,因为我们i+1->i,会变得是所有dis值,而这个下取整只有在是k的倍数的时候会发生变化:正好减少了1
用1当做根,式子变成了$$a_v*(\lfloor \frac{h-dep_{j}+dep_i}{k} \rfloor+1)$$
也就是说,我们维护一个数组表示等于深度i的所有的点系数和是什么
然后每次向前移动的时候,我们让i号点的答案对应加上一个数就好,应该是的那个j
树是一样的,我们会发现把这个树点分治后,同一深度上的点对于某个点的贡献是完全一样的
就是他们后面那个东西是一样的,前面的系数求个和就可以用表示深度为i这一层的点对于某个点贡献和就好了qwq
于此同时,我们可以继续在深度数组上做这个类似于链的推进过程:
维护深度与i同余的所有点系数和
维护深度为i的点受到其他所有点的影响之和
随着深度变小,不难发现后面的那个变量会变大变大,所以我们一样的从大到小推
注意h可能很大,超过我们能开的数组的范围,此时我们要减少一个k的倍数使得h在maxd范围内,而且要尽可能大
有:
而我们又有
证明如下:
如果A是x的倍数,可以直接打开下取整上取整号,结论显然成立
如果A不是x的倍数
=\lfloor \frac{A+x-1}{x}\rfloor$$(因为不是倍数) code: ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long const int MAXN = 3e5 + 7; int n, K, H, ccnt, rt, N; int a[MAXN]; vector<int> e[MAXN]; int siz[MAXN], dp[MAXN], vis[MAXN]; namespace fastIO { #define BUF_SIZE (1<<20) static char buf[BUF_SIZE], *p1 = buf, *pend = buf; inline char nc() { if(p1 == pend) { p1 = buf; pend = buf + fread(buf, 1, BUF_SIZE, stdin); } return *p1++; } inline int read() { int x = 0; char s = nc(); for(; !isdigit(s); s = nc()); for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0'; return x; } } using namespace fastIO; int mxd; ll suma[MAXN], qwq[MAXN], w[MAXN], sum[MAXN]; inline void getrt(int u, int F) { siz[u] = 1; dp[u] = 0; for(auto v : e[u]) { if(v == F || vis[v])continue; getrt(v, u); siz[u] += siz[v]; dp[u] = max(dp[u], siz[v]); } dp[u] = max(dp[u], N - siz[u]); if(dp[u] < dp[rt])rt = u; } ll ans = 1e18; inline void getans(int u, int F, int dep) { if(dep > H)return ; ans = min(ans, sum[u]); for(auto v : e[u]) { if(v == F)continue; getans(v, u, dep + 1); } return; } inline void getdis(int u, int F, int dep) { mxd = max(mxd, dep); suma[dep] += a[u]; for(auto v : e[u]) { if(vis[v] || v == F)continue; getdis(v, u, dep + 1); } } inline void getw(int u, int F, int dep, int t) { sum[u] += w[dep] * t; for(auto v : e[u]) { if(v == F || vis[v])continue; getw(v, u, dep + 1, t); } } inline void clr() { for(int i = 0; i <= mxd; ++i)suma[i] = qwq[i] = w[i] = 0; mxd = 0; } inline void solve2(int u, int t) { mxd = 0; getdis(u, u, t == 1 ? 0 : 1); mxd = min(mxd, H); for(int i = 0; i <= mxd; ++i)qwq[i] = suma[i] + (i >= K ? qwq[i - K] : 0); for(int i = 0; i <= mxd; ++i) { if((H - mxd - i) >= 0)w[mxd] += suma[i] * ((H - mxd - i) / K + 1);//下取整啊 } for(int i = mxd - 1; i >= 0; --i) { w[i] = w[i + 1]; if(H - i <= mxd)w[i] += qwq[H - i]; else { int qaq = (H - i - mxd + K - 1) / K; if(H - qaq * K - i >= 0)w[i] += qwq[H - qaq * K - i]; } } if(H % K == 0)w[0] -= qwq[0]; getw(u, u, t == 1 ? 0 : 1, t); clr(); } inline void solve(int u) { vis[u] = 1; solve2(u, 1); for(auto v : e[u]) { if(vis[v])continue; solve2(v, -1); rt = 0; N = siz[v]; getrt(v, u); solve(rt); } return; } int main() { n = read(); K = read(); H = read(); for(int i = 1; i <= n; ++i)a[i] = read(); for(int i = 1, x, y; i < n; ++i) { x = read(); y = read(); e[x].emplace_back(y); e[y].emplace_back(x); } rt = 0; N = n; dp[0] = N; getrt(1, 1); solve(rt); getans(1, 1, 0); printf("%lld\n", ans); return 0; } ``` 耗时1天半完结/kk