[人工智能][WC2022-DMY]Poborcy podatkowi

题目

传送门 to usOJ

题目描述
给出一棵树，边有边权。请你找出一些边不交的长度为 $4$ 的路径，使得权值和最大。输出答案。

数据范围与提示
$n?2\times 10^5$，边权 $w\in [?10^9,10^9]$ 。

思路

显然的 $\mathtt{d}\mathtt{p}$，设 $f(x,j)$ 表示 $x$ 点处有长度为 $j$ 的 “残链”，最大权值和。难点只在于转移。以 $f(x,0)$ 为例，先 列举我们需要的条件（这有助于分析）：

• 接到这个点上的长度为 $1$ 的链、为 $3$ 的链数量相同。
• 长度为 $2$ 的链的数量为偶数。

第二个容易记录。第一个相当于 $cn{t}_1?cn{t}_3=0$ 。左式范围是 $[?n,n]$，怎么办？用这道题的想法，$\text{shuffle}$ 一下。我本以为这是乱搞做法，没想到它有数学依据；是不是数学家就喜欢干这种事情：用我看不懂的公式解释我理解不了的现象，让我大受震撼？

我今天才知道，有一个东西叫 霍夫丁不等式（$\text{Hoeffding’s?inequality}$）：对于 $n$ 个独立随机变量 $x_1,x_2,x_3,\dots ,x_n$，设 $\mathbb{P}(x_i\in [a_i,b_I])=1$，记 $S_n={\sum }_{i=1}^n{x}_i$，则有
$$\mathbb{P}\left(\right|S_n?E[S_n]|?t)?2\exp \left(\frac{?2t^2}{n(b?a{)}^2}\right)$$
在本题中就直接套公式吧。由于 $1,3$ 数量相同，$\mathtt{s}\mathtt{h}\mathtt{u}\mathtt{f}\mathtt{f}\mathtt{l}\mathtt{e}$ 后近似于各有 $\frac{1}{2}$ 概率出现，为了方便，就规定为 $?1$ 和 $+1$ 。于是 $E[S_n]=0$，代入 $a=?1,b=+1$ 则
$$\mathbb{P}(|S_n|?t)?2\exp \left(\frac{?t^2}{2n}\right)$$
那么，在 $t=\lambda \sqrt{n}$ 时，概率的上界已经缩小到 $2\exp (?\frac{{\lambda }^2}{2})$，很难的啦！取 $\lambda =5$ 之类的，概率已经缩小到 $7\times 10^{?6}$，不太可能的啦！

所以复杂度是 $\mathcal{O}(n\sqrt{n})$ 。但是上面的不等式为啥是正确的，俺也不知道。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <random>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void getMax(llong &a,const llong &b){
	a ^= ((a-b)>>63)&(b^a); // when a-b < 0, do this
}

const int MAXN = 200005, SQRTN = 450;
const llong INF = (1ll<<60)-1;
llong dp[2][SQRTN<<1|1], tmp[2][SQRTN<<1|1];
int gh[MAXN]; llong f[MAXN][4];
vector< pair<int,int> > G[MAXN];
std::mt19937 rnd;
void solve(int x,int pre){
	if(!G[x].empty() && G[x][0].first == pre)
		G[x].erase(G[x].begin()); // special case
	for(auto it=G[x].begin(); it!=G[x].end(); ++it)
		if(it->first == pre) G[x].erase(it --);
		else solve(it->first,x); // recurse
	const int LEN = gh[G[x].size()];
	shuffle(G[x].begin(),G[x].end(),rnd);
	rep(o,0,1) fill(dp[o],dp[o]+(LEN<<1|1),-INF);
	dp[0][LEN] = 0; // origin of the world
	for(const auto &y : G[x]){
		rep(o,0,1) rep(j,0,LEN<<1){
			tmp[o][j] = dp[o][j]+max(f[y.first][0],f[y.first][3]+y.second);
			if(j) getMax(tmp[o][j],dp[o][j-1]+f[y.first][0]+y.second);
			getMax(tmp[o][j],dp[o^1][j]+f[y.first][1]+y.second);
			getMax(tmp[o][j],dp[o][j+1]+f[y.first][2]+y.second);
		}
		rep(o,0,1) memcpy(dp[o],tmp[o],(LEN<<1|1)<<3);
	}
	f[x][0] = dp[0][LEN], f[x][1] = dp[0][LEN+1];
	f[x][2] = dp[1][LEN], f[x][3] = dp[0][LEN-1];
}

int main(){
	int n = readint();
	for(int i=1,a,b,c,v=1; i!=n; gh[i]=v,++i){
		a = readint(), b = readint(), c = readint();
		G[a].push_back(make_pair(b,c));
		G[b].push_back(make_pair(a,c));
		if((v+1) <= i/(v+1)) ++ v; // one at a time
	}
	rep(i,1,10000) gh[i] = 100;
	gh[0] = 1; solve(1,-1);
	printf("%lld\n",f[1][0]);
	return 0;
}