题解 CF1214H 【Tiles Placement】

· · 题解

CF1214H Tiles Placement解题报告：

更好的阅读体验

题意

分析

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

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

先给出结论：

$k>2$时，我们看一看图： ![](https://fp1.fghrsh.net/2020/10/08/7700b412c89bab2b2cd0c832b3d4922c.png) 设$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$的链一定都在直径上，所以我们先对直径进行染色。 我们考虑剩下的点如何染色——剩下的点一定可以从直径上的颜色地推下来。 但是有一点细节要注意： ![](https://fp1.fghrsh.net/2020/10/08/67063642e456f8bbb146ec1e147d77a4.png) 如图，$k=4$，此时假设我们选择的直径为$(1,6)$，那么$(1,7),(3,6),(3,7)$这些路径的染色搭配也要考虑。 我们可以取直径中点$mid$，直径上$mid$左边的点可以采用颜色不断加$1$的染色策略，$mid$及右边的点可以采用颜色不断减$1$的染色策略，这样$mid$左右两点产生的路径我们都可以满足条件了。 复杂度：$O(n)$。 ## 代码 代码找了好久错，结果是$\text{getlen}$的递归调用了$\text{dfs}$（捂脸）。 注意特判$\text{m=2} 
#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;
}