#C241029C. 贝斯(bass)

标签（Label）

• 动态规划

网址（Website）

「PA 2021」Poborcy podatkowi

题目详情 - 贝斯(bass) - Super

题解 - 贝斯(bass) - Super

题目（Problem）

样例

输入数据 1

8
1 3 4
1 2 7
2 4 1
2 5 -3
3 7 1
4 6 2
5 8 9

输出数据 1

17

样例1解释

选择链 $3\sim8$，权值为 $17$。

输入数据 2

6
1 2 2
2 3 -1
3 4 -1
4 5 -1
5 6 2

输出数据 2

0

样例2解释

容易发现，每一条长度为 $4$ 的链权值均为负数。

输入数据 3

19
1 2 1
2 3 2
3 4 -1
4 5 -1
5 6 2
6 7 11
7 8 12
8 9 13
9 10 14
11 12 3
12 13 0
13 14 0
14 15 0
15 16 1
16 4 0
4 17 0
17 18 0
18 19 2

输出数据 3

57

样例3解释

1. 选择链 $2\sim6$，权值为 $2$；
2. 选择链 $6\sim10$，权值为 $50$；
3. 选择链 $11\sim15$，权值为 $3$；
4. 选择链 $16\sim19$，权值为 $2$。

样例4∼5

见选手目录下的 bass/bass[4-5].in 与 bass/bass[4-5].ans。给出的两个样例分别满足测试点 $8,11\sim12$ 的性质。

数据规模与约定

对于 $100%$ 的数据，$1 \leq n \leq 2 \times 10^5$；$|w_i| \leq 10^9$。

各测试点的附加限制如下表所示：

测试点编号	$n \leq$	特殊性质
1	$4$
2	$8$
3∼4	$16$
5∼6	$23$
7	$50$
8	$500$
9∼10	$5000$
11∼12	$5 \times 10^4$	A
13	$5 \times 10^4$
14	$10^5$
15	$1.3 \times 10^5$
16	$1.6 \times 10^5$
17	$1.75 \times 10^5$
18	$1.9 \times 10^5$
19∼20	$2 \times 10^5$

特殊性质 $A$：$\forall 1 \leq i < n, u_i = i, v_i = i + 1$。

题解（Solution）

出题者题解

算法分析

【算法一】

状压 $dp$，观察到很多状态是没用的，可以丢了。

时间复杂度 $O(?)$，可以通过测试点 $1\sim6$，期望得分根据实现 $0\sim30$。

【算法二】

当树退化为链时，设 $f_i$ 表示前 $i$ 条边的答案，有转移：

$f_i = \min(f_{i-1}, f_{i-4} + \sum_{i-3}^{i})$

时间复杂度：$O(n)$，可以通过测试点 $11\sim12$，期望得分 $10$。

结合算法一可以得到 $40$ 分。

【算法三】

树形 $dp$，设 $f_{i,0/1/2/3}$ 表示 $i$ 子树，延伸上来的链长度为 $0/1/2/3$ 的答案。

转移为给每个儿子选择 $0/1/2/3$ 中的一个数，然后 $2,2$ 和 $1,3$ 都可以匹配掉，求最后只剩下 $1,2,3$ 中一个数的答案。

设 $g_{t,i,j,k}$ 表示前 $t$ 个数选择的 $1,2,3$ 的个数，转移 $O(1)$，时间复杂度 $O(n^4)$。

由于 $2,2$ 可以匹配，于是状态可以简化为 $g_{t,i,0/1,k,0/1}$ 表示 $2$ 选择个数的奇偶性，时间复杂度 $O(n^3)$。

由于 $1,3$ 可以匹配，于是状态可以简化为 $g_{t,i,0/1}$，$i$ 表示 $1,3$ 选择个数之差，时间复杂度 $O(n^2)$。

实现的优秀一点可以通过 $n \leq 5 \times 10^4$，过到测试点 $13$，期望得分根据实现 $35\sim65$。

【算法四】

考虑优化算法三，由于最后 $i = -1/0/1$ 时才会合法，我们把 $1$ 视作 $1$，$3$ 视作 $-1$，也就是说 $1,-1$ 的总和是 $O(1)$ 的。

将每个节点的所有儿子 random_shuffle，有结论：$1,-1$ 前缀和最大值的期望为 $O(\sqrt{n})$。

感性理解确实不会很大，理性证明：

定理3.2： 有一个随机数生成器，返回的数字在 $[A,B]$ 之间，期望为 $E_0$，方差为 $\sigma^2$。那么随机 $N$ 次，求出返回数的平均值，设与 $E_0$ 的绝对误差为 $\delta$，那么几乎一定有 $\delta < O(\sigma N^{-\frac{1}{2}})$。

证明： 设绝对误差为 $\delta = \left| \frac{a_1 + a_2 + \cdots + a_N}{N} - E_0 \right|$。考虑对任意常数 $c$，求出

$Pr(\delta > c \cdot \sigma N^{-\frac{1}{2}})$

由 Hoeffding’s inequality：

$Pr\left(\delta N > c \cdot \sigma N^{\frac{1}{2}}\right) \leq 2 \exp\left(-\frac{2(c-1)^2 \sigma^2 N}{N(B-A)^2}\right)= 2 \exp\left(-\frac{2(c-1)^2 \cdot \sigma^2}{(B-A)^2}\right)$

是一个与 $N$ 无关的常数且随 $c$ 增大指数级缩小。证毕。

有可能看不懂，但你会大受震撼！考场上可以考虑写个随机跑一下期望。

回到 $dp$，也就是说 $g_{t,i,0/1}$ 的第二维 $i$ 只需要开到 $[-n,n]$。

时间复杂度 $O(n^2)$，期望得分 $100$。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i==)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 401234;
const int B = 800;
bool ST;
mt19937_64 rr(time(0));
vector<P> ft[N];
int n;

inline void cmx(int &x, int y){x=min(x,y);}

int f[N][4],g[2][N*2][2];
void dfs_ans(int x,int fa,int lstv){
	vector<int> son;
	for(auto p:ft[x]){
		int y=p.x,v=p.y;
		if(y==fa)continue;
		dfs_ans(y,x,v);
		son.emplace_back(y);
	}
	For(i,-2,2) For(t,0,1) g[0][n+i][t] = -inf;
	g[0][n][0] = 0;
	
	int scnt=0,cnt=0,p,b;
	shuffle(son.begin(),son.end(),rr);
	for(auto y:son){
		assert(y^fa);
		scnt++, cnt++;
		cnt = min(cnt, 500ll);
		p = scnt&1, b = p^1;
		For(i,n-cnt,n+cnt){
			For(t,0,1){
				g[p][i][t] = max(-inf, g[b][i][t]+f[y][0]);
				g[p][i][t] = max(g[p][i][t], g[b][i-1][t]+f[y][1]);
				g[p][i][t] = max(g[p][i][t], g[b][i][t^1]+f[y][2]);
				g[p][i][t] = max(g[p][i][t], g[b][i+1][t]+f[y][3]);
			}
		}
		if(cnt==scnt)
			For(i,1,2) For(t,0,1) g[p][n-scnt-i][t] = g[p][n+scnt+i][t] = -inf;
	}
	if(scnt){
		f[x][0] = max(g[p][n][0], g[p][n+1][0]+lstv);
		f[x][1] = g[p][n][1] + lstv;
		f[x][2] = g[p][n-1][0] + lstv;
		f[x][3] = g[p][n][0] + lstv;
	}else{
		f[x][0] = 0;
		f[x][1] = -inf;
		f[x][2] = -inf;
		f[x][3] = lstv;
	}
}

void Solve(){
	n = rd();For(i,1,n-1){
		int x=rd(),y=rd(),v=rd();
		ft[x].emplace_back(y,v);
		ft[y].emplace_back(x,v);
	}
	dfs_ans(1,0,-inf);
	printf("%lld\n", f[1][0]);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("bass.in","r",stdin);
	freopen("bass.out","w",stdout);
	int T=1;double Tim=clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}