CF830E Perpetual Motion Machine

· · 题解

先假设图是联通的。

如果 m\ge n，那么 \forall u,d_u=1 即可。

由于图联通，所以 m\ge n-1。

于是我们只需要考虑 m=n-1 的情况，也就是一棵树。

令 V 表示所有点组成的集合，P(u,v) 表示 u\rightarrow v 的路径上经过的点组成的集合。

如果 \exists u,deg_u\ge 4，那么 d_u=2,\forall v\neq u,d_v=1 即可。

如果 \exists u,v,deg_u=deg_v=3，那么 \forall w\in P(u,v),d_w=2,\forall w\notin P(u,v),d_w=2 即可。

如果 \forall u,deg_u\le 2，那么树退化成一条链，利用排序不等式可证明一定无解。

剩下的情况就是 \exists u,deg_u=3，且 \forall v\neq u,deg_v\le 2。

容易发现这种情况下树的形态一定是从 u 连出去 3 条链。

设 3 条链为 L_1,L_2,L_3,S_i=\sum\limits_{u\in L_i} a_u。不妨令 u 为根，|L_1|\le |L_2|\le |L_3|。

再设 a_v=d_vd_{fa_v}-d_v^2。特殊地，a_u=0。

那么我们就是要令 S=\sum a_u-d_u^2\ge 0。

对于一条链上的连续 3 个点 v_1,v_2,v_3。

a_{v_2}+a_{v_3} =d_{v_1}d_{v_2}+d_{v_2}d_{v_3}-d_{v_2}^2-d_{v_3}^2 =-d_{v_2}^2+(d_{v_1}+d_{v_3})d_{v_2}-d_{v_3}^2

可以发现，如果固定 d_{v_1},d_{v_3}，那么 d_{v_2}=\dfrac{d_{v_1}+d_{v_3}}{2} 时上式取到最大值。

也就是说，对于 L_i，S_i 取到最大值时这条链上的 d 值一定从下到上成为一个递增的等差数列，但此时公差不好确定。

不妨在 L_i 的叶子下面接上一个 0，显然不影响答案，此时就可以确定公差 c_i=\dfrac{d_u}{|L_i|+1}。我们先忽略 c_i 可能为小数的事实。

于是可以得出 S_i=c_i^2\dfrac{|L_i|(|L_i|+1)}{2}=d_u^2\dfrac{|L_i|}{2(|L_i|+1)}。

S\ge 0 \sum S_i-d_u^2\ge 0 \sum d_u^2\dfrac{|L_i|}{2(|L_i|+1)}-d_u^2\ge 0 \sum\dfrac{1}{|L_i|+1}\le 1

我们再尝试进行构造。

综上，我们找到了图联通时的构造方法，正确性显然。

如果图不联通就对于每一个连通块做一遍。如果存在某一个连通块合法，那么就按照上述方法构造，并把其它连通块全部赋为 0，否则无解。

时间复杂度 O(n) 或 O(n\alpha(n))，取决于是否使用并查集。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define pb push_back
int T,n,m,ps,nw,fa[N],fa1[N],lst[N],ans[N];vector<int> z[3],e[N];
int findRt(int u) {return u==fa[u]?u:fa[u]=findRt(fa[u]);}
bool merge(int u,int v)
{u=findRt(u);v=findRt(v);if(u==v) return 0;fa[u]=v;return 1;}
void dfs(int u,int f) {fa1[u]=f;for(auto v:e[u]) if(v!=f) dfs(v,u);}
void dfs1(int u,int f)
{
    if(f) z[nw].pb(u);if(e[u].size()==1) ++nw;
    for(auto v:e[u]) if(v!=f) dfs1(v,u);
}
void slv()
{
    scanf("%d %d",&n,&m);ps=0;for(int i=1;i<=n;++i) fa[i]=i,e[i].clear();
    for(int i=1,u,v;i<=m;++i)
    {scanf("%d %d",&u,&v);e[u].pb(v);e[v].pb(u);if(!merge(u,v)) ps=u;}
    if(ps)
    {
        puts("YES");
        for(int i=1;i<=n;++i) printf("%d ",findRt(ps)==findRt(i));
        puts("");return;
    }ps=0;for(int i=1;i<=n;++i) if(e[i].size()>3) ps=i;
    if(ps)
    {
        puts("YES");
        for(int i=1;i<=n;++i) printf("%d ",ps==i?2:(findRt(ps)==findRt(i)));
        puts("");return;
    }for(int i=1;i<=n;++i) lst[i]=ans[i]=0;
    for(int i=1,t;i<=n;++i) if(e[i].size()>2)
    {
        t=findRt(i);if(!lst[t]) {lst[t]=i;continue;}
        dfs(i,0);for(int j=lst[t];j;j=fa1[j]) ans[j]=2;puts("YES");
        for(int j=1;j<=n;++j) printf("%d ",ans[j]?2:(findRt(i)==findRt(j)));
        puts("");return;
    }
    for(int i=1;i<=n;++i) if(e[i].size()>2)
    {
        nw=0;z[0].clear();z[1].clear();z[2].clear();dfs1(i,0);
        if(z[0].size()>z[1].size()) swap(z[0],z[1]);
        if(z[0].size()>z[2].size()) swap(z[0],z[2]);
        if(z[1].size()>z[2].size()) swap(z[1],z[2]);
        if(z[0].size()>1)
        {
            ans[i]=3;ans[z[0][0]]=ans[z[1][0]]=ans[z[2][0]]=2;
            ans[z[0][1]]=ans[z[1][1]]=ans[z[2][1]]=1;
            puts("YES");for(int j=1;j<=n;++j) printf("%d ",ans[j]);puts("");return;
        }
        if(z[1].size()>2)
        {
            ans[i]=4;ans[z[0][0]]=2;ans[z[1][0]]=ans[z[2][0]]=3;
            ans[z[1][1]]=ans[z[2][1]]=2;ans[z[1][2]]=ans[z[2][2]]=1;
            puts("YES");for(int j=1;j<=n;++j) printf("%d ",ans[j]);puts("");return;
        }if(z[1].size()<2) continue;
        if(z[2].size()>4)
        {
            ans[i]=6;ans[z[0][0]]=3;ans[z[1][0]]=4;ans[z[1][1]]=2;
            ans[z[2][0]]=5;ans[z[2][1]]=4;ans[z[2][2]]=3;ans[z[2][3]]=2;ans[z[2][4]]=1;
            puts("YES");for(int j=1;j<=n;++j) printf("%d ",ans[j]);puts("");return;
        }
    }puts("NO");
}
int main() {scanf("%d",&T);while(T--) slv();return 0;}