P9047

现在题解区只有一篇 $O(n\log n)$ 做法，而且是闵可夫斯基和，完全不会。于是讲另一种 $O(n\log n)$ 做法。

首先写 $O(n^2)$ 的树形 dp：设 $dp_{u,i}$ 为处理完 $u$ 的子树，现在 $u$ 处挂着一条长为 $i$ 的链，答案的最大值。这里包含 $(u,fa_u)$ 这条边。

转移的话，对于一个 $u$ ，设 $f_{i,0/1,0/1/2/3}$ 表示当前已经枚举到的 $u$ 的儿子中，选长度为 $1$ 的和长度为 $3$ 的链的数量的差为 $i$ ，选了偶数/奇数个长度为 $2$ 的，钦定 $u$ 处挂着一条长度为 $0/1/2/3$ 的链。每次枚举到一个儿子就根据这个儿子处挂一条长度为多少的链转移。

然后考虑优化。注意到我们最后求的是 $f_{0,0,0/1/2/3}$ 的最值，但是我们需要 $i\not=0$ 的位置中间转移。于是想到 wqs 二分。

众所周知 wqs 二分要求 $f(i,*)$ 是凸的。但是这一步我不太会严谨证。不过可以感性理解：考虑如果把所有 $dp_{v,1}$ 加上 $\Delta>0$ ， $dp_{v,3}$ 减去 $\Delta$ ，那么选的长度为 $1$ 的链会随着 $k$ 增大而增加。

于是先确定挂在 $u$ 上的链长度 $l$ ，二分一个 $\Delta$ ，然后再进行一个 dp：设 $f_{i,0/1,0/1,0/1}$ 表示当前处理到第 $i$ 个儿子，选了奇数/偶数个 $2$ ，奇数/偶数个 $1$ 或 $3$ ，是否已经选出了挂在 $u$ 上的链。转移类似，不过还要对每个状态记录这个状态对应选了多少 $1$ 和 $3$ 。最后看最优情况下是否选的 $1$ 多于选的 $3$ 。

到这里其实就算是解决了，但是 wqs 二分很重要的就是一堆细节。这题更是如此：

wqs 二分的方式一定是 $dp_{v,1}$ 加， $dp_{v,3}$ 减，而不能是只有 $dp_{v,1}$ 加，否则会取更少的 $(1,3)$ 对。
最后一定是选的 $1$ 数量大于等于选 $3$ 的就返回 true。原因显然。
如果遇到被更新的值等于要更新它的值，优先选选的 $1$ 更多的，选相同 $1$ 的情况下，选 $3$ 更少的。注意是更少的！似乎是因为这样才能凑出更多 $(1,3)$ 对。
二分上下界大概要开到 $[-10^{12},10^{12}]$ ， $[-10^9,10^9]$ 不够。
注意到有时候可能需要让 $\Delta$ 有小数部分（事实上 wqs 二分理论上都是需要二分小数，毕竟是斜率），不过只有可能加上 $0.5$ ，所以先把所有 $w\to w\times 2$ ，最后再将答案 $\times \frac{1}{2}$ 即可。
$1$ 号点上面没有边了，注意特判。

时间复杂度 $O(n\log V)$ 。但是我的这种 $n^2$ 暴力 dp 常数大，导致最后代码常数也大。似乎有常数小写法？

code：

int n,m,deg[N],g[N][2][2][2],h[N][2][2][2];
ll f[N][2][2][2],dp[N][4];
int U;
int tot,head[N];
struct node{
	int to,nxt,cw;
}e[N<<1];
il void add(int u,int v,int w){
	e[++tot]={v,head[u],w},head[u]=tot;
}
il void upd(int i,int j,int k,int l,ll w,int p,int q,int op,int x,int y){
	if(w>f[i][j][k][l]||w==f[i][j][k][l]&&x+p>g[i][j][k][l]||w==f[i][j][k][l]&&x+p==g[i][j][k][l]&&y+q<h[i][j][k][l]){
		f[i][j][k][l]=w;
		if(op==0){
			g[i][j][k][l]=g[i-1][j][k][l]+p;
			h[i][j][k][l]=h[i-1][j][k][l]+q;
		}else if(op==1){
			g[i][j][k][l]=g[i-1][j^1][k][l]+p;
			h[i][j][k][l]=h[i-1][j^1][k][l]+q;
		}else if(op==2){
			g[i][j][k][l]=g[i-1][j][k][0]+p;
			h[i][j][k][l]=h[i-1][j][k][0]+q;
		}else{
			g[i][j][k][l]=g[i-1][j][k^1][l]+p;
			h[i][j][k][l]=h[i-1][j][k^1][l]+q;
		}
	}
}
bool check(ll k,vector<int> &vec,int p,int w){
	int m=(int)vec.size()-1;
	rep(i,0,m){
		rep(j,0,1){
			rep(l,0,1){
				rep(q,0,1){
					f[i][j][l][q]=-1ll*inf*inf;
					g[i][j][l][q]=h[i][j][l][q]=0;
				}
			}
		}
	}
	f[0][0][0][0]=0;
	if(p==1){
		f[0][0][0][1]=w;
	}
	rep(i,1,m){
		rep(j,0,1){
			rep(l,0,1){
				rep(q,0,1){
					upd(i,j,l^1,q,f[i-1][j][l][q]+dp[vec[i]][1]+k,1,0,3,g[i-1][j][l][q],h[i-1][j][l][q]);
					upd(i,j,l^1,q,f[i-1][j][l][q]+dp[vec[i]][3]-k,0,1,3,g[i-1][j][l][q],h[i-1][j][l][q]);
					upd(i,j,l,q,f[i-1][j][l][q]+dp[vec[i]][0],0,0,0,g[i-1][j][l][q],h[i-1][j][l][q]);
					upd(i,j^1,l,q,f[i-1][j][l][q]+dp[vec[i]][2],0,0,1,g[i-1][j][l][q],h[i-1][j][l][q]);
					if(!q&&p){
						upd(i,j,l,1,f[i-1][j][l][q]+dp[vec[i]][p-1]+w,0,0,2,g[i-1][j][l][q],h[i-1][j][l][q]);
					}
					
				}
			}
		}
	}
	return g[m][0][0][min(p,1)]>=h[m][0][0][min(p,1)];
}
void dfs(int u,int fa,int w){
	vector<int> vec;
	vec.eb(0);
	int m=0;
	go(i,u){
		int v=e[i].to;
		if(v==fa){
			continue;
		}
		dfs(v,u,e[i].cw);
		vec.eb(v),m++;
	}
	rep(i,0,3){
		dp[u][i]=-1ll*inf*inf;
	}
	U=u;
	rep(i,0,fa?4:0){
		ll l=-1e12,r=1e12,ans=0;
		while(l<=r){
			ll mid=(l+r)>>1;
			if(check(mid,vec,i,w)){
				ans=mid;
				r=mid-1;
			}else{
				l=mid+1;
			}
		}
		check(ans,vec,i,w);
		dp[u][i%4]=max(dp[u][i%4],f[m][0][0][min(i,1)]);
	}
}
void Yorushika(){
	read(n);
	rep(i,1,n-1){
		int u,v,w;read(u,v,w),w*=2;
		add(u,v,w),add(v,u,w);
		deg[u]++,deg[v]++;
	}
	dfs(1,0,0);
	printf("%lld\n",dp[1][0]/2);
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

感谢您的支持，我会继续努力的!