CF1214H Tiles Placement解题报告

解题报告

CF1214H Tiles Placement解题报告：

更好的阅读体验

题意

• 给定一棵$n$个点的树，可以用$k$种颜色染色；
• 你需要判断是否存在一种染色方案满足任意长度为$k$的链必须包含$k$种颜色；
• 若有方案，则输出"Yes"，并任意输出一种方案；否则输出"No"。
• $1\leqslant n\leqslant 2\cdot 10^5,2\leqslant k\leqslant n$。

分析

最近听了一个神仙讲了这道题，就来做一做。

一道找规律神题，现场推出了和正解等价的规律，但是还是不会。

先给出结论：

• $k=2$时，一定存在这样的染色方案，只需要按照深度交替染色就可以了；
• $k>2$时，若存在$3$个点距离大于等于$k$，那么不存在染色方案。

$k=2$时，结论显然成立。

$k>2$时，我们看一看图：

设$a$到$x$距离为$len_a$，$b$到$x$距离为$len_b$，$c$到$x$距离为$len_c$。

如果$len_a+len_b\geqslant k$，$len_a+len_c\geqslant k$，$len_b+len_c\geqslant k$，那么我们任取$a$到$x$链上一点$p$，$b$到$x$链上一点$q$，$c$到$x$链上一点$r$，使$p$到$q$的距离为$k$，$q$到$r$的距离为$k$。

我们令$p$到$q$链上已经确定了染色方案，那么$p$到$x$的染色方案递推到$r$的方案，一定与$q$到$x$的染色方案递推到$r$的方案不同，于是我们推出了矛盾。

因此结论成立。

我们考虑取出直径（这里取出直径主要是为了解决第二问），求出每个点不向直径扩展的最长链和次长链，并对于直径上的点和直径外的点分类讨论：
（下面的最长链与次长链均指不向直径扩展的链）

• 对于所有的$x$，如果最长链与次长链合并后长度大于等于$k$，那么不能构造方案。（设最长链的链底为$p_1$，次长链的链底为$p_2$，则直径两个端点中的一个一定可以与$p_1$和$p_2$构成两两距离大于等于$k$的三个点）
• 若$x$在直径上，如果最长链与$x$分隔开的直径两段合并后长度均大于等于$k$，那么不能构造方案。（最长链链底和直径的两端可以构成两两距离大于等于$k$的三个点）

这样，我们就判断出了是否可以进行构造。

构造方法比较显然：

首先，因为在满足上述要求下，长度大于等于$k$的链一定都在直径上，所以我们先对直径进行染色。

我们考虑剩下的点如何染色——剩下的点一定可以从直径上的颜色地推下来。

但是有一点细节要注意：

如图，$k=4$，此时假设我们选择的直径为$(1,6)$，那么$(1,7),(3,6),(3,7)$这些路径的染色搭配也要考虑。

我们可以取直径中点$mid$，直径上$mid$左边的点可以采用颜色不断加$1$的染色策略，$mid$及右边的点可以采用颜色不断减$1$的染色策略，这样$mid$左右两点产生的路径我们都可以满足条件了。

复杂度：$O(n)$。

代码

代码找了好久错，结果是$\text{getlen}$的递归调用了$\text{dfs}$（捂脸）。

#include<stdio.h>
#define inf 1000000000
const int maxn=200005,maxm=maxn<<1;
int n,m,e,s1,s2,s,maxx,col,flg,mid;
int start[maxn],to[maxm],then[maxm];//链式前向星
int dep[maxn],f[maxn],ans[maxn],flen[maxn],slen[maxn];//深度，递归时的父亲，染的颜色，最长链，次长链
inline void add(int x,int y){//加边
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void dfs(int x,int last){
    f[x]=last,dep[x]=dep[last]+1;
    flen[x]=slen[x]=0;
    if(dep[x]>maxx)
        maxx=dep[x],s=x;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
    }
}
void getlen(int x,int last){
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last||ans[y])
            continue;
        getlen(y,x);
        if(flen[y]+1>flen[x])
            slen[x]=flen[x],flen[x]=flen[y]+1;
        else if(flen[y]+1>slen[x])
            slen[x]=flen[y]+1;
        if(slen[y]+1>slen[x])
            slen[x]=slen[y]+1;
    }
}
void solve(int x,int c,int t){//染色，其中t=1时颜色为父亲的颜色+1，t=-1时相反
    ans[x]=c;
    c=(c+t+m-1)%m+1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(ans[y]!=0)
            continue;
        solve(y,c,t);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    maxx=-inf,dfs(1,0),s1=s;//s1为直径一个端点
    maxx=-inf,dfs(s,0),s2=s;//s2为直径另一端点
    if(m==2){//特判m=2
        puts("Yes");
        for(int i=1;i<=n;i++)
            printf("%d%c",dep[i]%2+1,i==n? '\n':' ');
        return 0;
    }
    for(int i=s2;i!=0;i=f[i]){//对直径染色
        col=col%m+1;
        if((dep[s1]+dep[s2])/2==dep[i])//找到中点
            mid=i;
        ans[i]=col;
    }
    for(int i=s2;i!=0;i=f[i]){//直径上的点向它不向直径扩展的子树中求最长/次长链
        getlen(i,0);
        if(ans[i]&&flen[i]&&dep[i]+flen[i]>=m&&(dep[s2]-dep[i]+1)+flen[i]>=m){
            puts("No");
            return 0;
        }
    }
    for(int i=1;i<=n;i++)
        if(flen[i]+slen[i]+1>=m){
            puts("No");
            return 0;
        }
    for(int i=s2;i!=mid;i=f[i])//直径前半段染色
        solve(i,ans[i],-1);
    for(int i=mid;i!=0;i=f[i])//直径后半段染色
        solve(i,ans[i],1);
    puts("Yes");
    for(int i=1;i<=n;i++)
        printf("%d%c",ans[i],i==n? '\n':' ');
    return 0;
}