题解：P13099 [FJCPC 2025] VERTeX

HPXXZYY · 2025-07-07 14:54:58 · 题解

如果可以知道一个点的点权的话，那么 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 次换根，如果都无法求出合法解，就认为不存在合法解。

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

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;
}