题解：P13099 [FJCPC 2025] VERTeX

\color{blue}{\texttt{[Analysis]}}

如果可以知道一个点的点权的话，那么

O(n)

的时间内我们可以把所有点的点权均求出来。

我们先考虑随机给点

1

赋上一个权值，那么可以把所有的

b_{u}^{1}

求出来。当然这未必是一个合法的方案。

显然，可能会存在某个或某些点

v

，使得

b_{v}^{1}\leq 0

。考虑换根，将其中一个

v

作为新的根，把它的点权取值为

1

，然后求出

b_{u}^{2}

。当然

b^{2}

中可能仍然存在小于等于

0

的点，把它作为根继续迭代。

可以预见，如果无解，那么无论谁作为根都求不出合法解出来；如果有解，可以在有限次数的换根中得到合法的解。

由于

n \leq 2 \times 10^{5}

，可以考虑进行

100

次换根，如果都无法求出合法解，就认为不存在合法解。

\color{blue}{\texttt{[Solution]}}

将 $1$ 作为原树的根节点。
将根节点的点权赋值为 $1$ 。
迭代求出所有点的点权。
检查点权方案是否合法。如果合法，则跳转至步骤 $6$ ；否则找到一个点权小于等于 $0$ 的点 $v$ 。
将 $v$ 作为新树的根。如果迭代次数超过限制，跳转至步骤 $7$ ；否则回到步骤 $2$ 。
输出合法方案，跳至步骤 $8$ 。
输出无解，跳至步骤 $8$ 。
程序结束。

\color{blue}{\text{Code}}

CPP

int val[N],n;
void dfs(int u,int Fa,int point){
	val[u]=point;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if (v==Fa) continue;
		
		dfs(v,u,e[i].val-point);
	}
}
int check(int rt){
	dfs(rt,0,1);
	for(int i=1;i<=n;i++)
		if (val[i]<=0) return i;
	return 0;
}

int main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read(),val=read();
		add(u,v,val);add(v,u,val);
	}
	
	int rt=1;
	for(int i=1;i<=100;i++){
		int rec=check(rt);
		if (!rec){
			printf("YES\n");
			for(int i=1;i<=n;i++)
				printf("%d ",val[i]);
			return 0;
		}
		rt=rec;
	}
	
	printf("NO");
	
	return 0;
}

题解：P13099 [FJCPC 2025] VERTeX

文章操作

相关推荐

评论

题解：P13099 [FJCPC 2025] VERTeX