差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/08/26 16:37]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/10/04 17:00] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-===== I. War of Inazuma (Hard Version) =====
+===== H. travel =====
 ==== 题意 ====
-要求给 $n$ 位二进制数染上黑白两色，使得黑白两色的二进制数个数不相等。同时每个二进制数向其他只有一位与自身不同的二进制数连边。
+给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。
-要求与每个二进制数相邻的同色二进制数不超过 $m=\lceil\sqrt n\rceil$。
 ==== 题解 ====
-将二进制数写成一个 $\lceil\frac nm\rceil\times m$ 的矩阵，最后一行不足的位置补 $1$，然后将二进制数分为四类：
+设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树，结点 $u$ 的状态为 $0/1/2$ 时，已经选中了 $i$ 条链此时的最大路径权值和。
-$A.$ 有奇数个 $1$，至少存在一行全为 $1$
+我们需要维护一条正在生成的链，这条链不包含在已经选中的 $i$ 条链当中，如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。
-$B.$ 有偶数个 $1$，不存在一行全为 $1$
+如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。
-$C.$ 有奇数个 $1$，不存在一行全为 $1$
+考虑状态转移，利用生成链的合并，不难有
-$D.$ 有偶数个 $1$，至少存在一行全为 $1$
+$$
+\text{dp}(u,0,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,0,j)\\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,1,j)+a_u\\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,0,j)\\
+\text{dp}(u,2,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,1,j)\\
+\text{dp}(u,2,i+j)\gets \text{dp}(u,2,i)+\text{dp}(v,0,j)
+$$
-$A,B$ 染白色，$C,D$ 染黑色。下面证明方案合法：
+注意上式的 $\gets$ 表示取最大值，另外为了防止选中复数条从 $v$ 生成的链，需要开一个临时数组存储中间量。
-只考虑白色的合法性，黑色的合法性是对称的。
+初始状态为 $\text{dp}(u,1,0)=a_u$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有
-首先 $A$，$B$ 内部不连边，因为内部 $1$ 奇偶性相同所有至少有两个位置不同。
+$$
+\text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1))
+$$
-只有仅一行全 $1$ 的 $A$ 才能和 $B$ 连边，否则至少有两个位置不同。
+最终答案为 $\text{dp}(1,0,3)$，时间复杂度 $O(nk^2)$，其中 $k$ 表示最多能选中的链的个数。
-对于 $A$ 仅一行全 $1$ 的数 $u$，为了和 $B$ 中的数 $v$ 连边，需要 $v$ 其他行与 $u$ 完全相同，然后 $v$ 在 $u$ 的全 $1$ 行只有一个位置是 $0$。
+[[http://tokitsukaze.live/2018/07/24/2018niuke2.H/|参考资料]]
-由于一行只有 $m$ 个数，于是这样的 $v$ 最多只有 $m$ 个。
-对与 $B$ 中的每个数 $u$，为了和 $A$ 中的数 $v$ 连边，需要 $v$ 其他行与 $u$ 完全相同，然后仅某一行是全 $1$ 行。
-由于只有 $\lceil\frac nm\rceil$ 行，因此这样的 $v$ 最多只有 $\lceil\frac nm\rceil\le m$ 个。
-最后有 $A+C=B+D=2^{n-1},B+C=(2^m-1)^{\lceil\frac nm\rceil}$，于是 $A+B,C+D$ 都是奇数。
-由于 $4\mid A+B+C+D$，于是 $A+B\neq C+D$。
 <hidden 查看代码>
 <code cpp>
-bool check(int n,int m,int v){
+const int MAXN=4e5+5,MAXK=4;
-	bool flag_cnt=false;
+struct Edge{
-	bool flag_one=false;
+	int to,next;
-	for(int i=0;i<n;i+=m){
+}edge[MAXN<<1];
-		bool flag_line=true;
+int a[MAXN],head[MAXN],edge_cnt;
-		int r=min(n,i+m);
+LL dp[MAXN][3][MAXK],tmp[3][MAXK];
-		_for(j,i,r){
+void Insert(int u,int v){
-			int c=v&1;
+	edge[++edge_cnt]=Edge{v,head[u]};
-			flag_line&=c;
+	head[u]=edge_cnt;
-			flag_cnt^=c;
+}
-			v>>=1;
+void Max(LL &a,LL b){
+	if(b>a)
+	a=b;
+}
+void dfs(int u,int fa){
+	dp[u][1][0]=a[u];
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs(v,u);
+		_for(i,0,3)_for(j,0,MAXK)
+		tmp[i][j]=dp[u][i][j];
+		_for(i,0,MAXK)_for(j,0,MAXK-i){
+			Max(tmp[0][i+j],dp[u][0][i]+dp[v][0][j]);
+			Max(tmp[1][i+j],dp[u][0][i]+dp[v][1][j]+a[u]);
+			Max(tmp[1][i+j],dp[u][1][i]+dp[v][0][j]);
+			Max(tmp[2][i+j],dp[u][1][i]+dp[v][1][j]);
+			Max(tmp[2][i+j],dp[u][2][i]+dp[v][0][j]);
 		}
-		flag_one|=flag_line;
+		_for(i,0,3)_for(j,0,MAXK)
+		dp[u][i][j]=tmp[i][j];
 	}
-	return flag_cnt^flag_one;
+	_for(i,1,MAXK)
+	Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1]));
 }
 int main()
 {
-	int n=read_int(),m=ceil(sqrt(n));
+	int n=read_int();
-	_for(i,0,1<<n)
+	_rep(i,1,n)
-	putchar('0'+check(n,m,i));
+	a[i]=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	dfs(1,0);
+	enter(dp[1][0][3]);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具