hihoCoder1462: Rikka with Tree IV

「パニッシュメント......ディス、ワールド!」

头图是贴来“激励” YZ 的。x2

传送门

题目大意

勇太有一棵有 $n$ 个节点的树。他想把每个节点染上一种颜色,并且使每一个大小不大于 $k$ 的连通子图中的每一个节点颜色都不同。

现在勇太想让六花求出他至少需要多少种颜色来给树染色。

其中 $1\le k\le n\le 10^5$。

【讲道理我觉得勇太不会这样对六花。。。

题解

讲道理我觉得一定有暴力能过这道题。

我的大致想法是存一个二维数组 $cnt[i]$ 表示距离当前节点为 $i$ 的节点编号,然后从父亲向儿子传递这个数组,之类的。。。

也许可以用 $vector$ 来乱搞?【树上启发式合并。

先来说一下这道题的思路吧。

这道题好难啊,不会啊。

怎么办呢?

那就试着把 $k$ 变小一点看看能不能简单点?


1. 简化问题

  • 当 $k=1$ 时:

    emmm.

    $1$?

    好像是。。。

  • 当 $k=2$ 时:

    emmm.

    $2$?

    好像是?

    其实并不是

    $n=1$ 时是 $1$。【手动滑稽。

  • 当 $k=3$ 时:

    emmm.

    不会。。。

    大胆猜测:$3$?

    小心求证:肯定不是嘛,随便搞一个菊花就可以了。。。而且菊花有多少个点就要多少颜色。

    嗯?等等等等。菊花好像就是一个?这个内所有节点颜色互不相同?

    好像是直径为 $2$ 的圆能包含的最多节点数?

    其实就是 $\max\{Degree_i\}+1$ 嘛。


2. 一些猜想

分析到 $k=3$,应该有一点感觉了。

大胆猜想:$k$ 为奇数时,答案为直径为 $k-1$ 的圆能覆盖的最多节点数。

必要性:若有两个点颜色相同且在同一圆中,它们之间的距离一定 $\le k-1$,这两点之间的链上最多有 $k-1+1=k$ 个点。如果选择这条链为子图满足“大小不大于 $k$”,且不满足“子图中每个节点颜色不同”。

充分性:对于每一个子图,因为大小不大于 $k$,所以子图中任意两点的距离一定 $\le k-1$,那么一定可以找到一个直径为 $k-1$ 的圆完全覆盖当前子图,而这个圆内所有点颜色不同。

诶?好像对了。

但是直径好像有点难,怎么统计?

好像是直径为 k-1 的圆能包含的最多节点数?

换成这样:好像是半径为 $\cfrac{k-1}{2}$ 的圆能包含的最多节点数?

emmm.

嗯?

对于每个点,统计距离它不大于 $\cfrac{k-1}{2}$ 的节点数量?

树分治。

那么 $k$ 为偶数该怎么办呢?

总觉得好像没法搞?

毕竟圆心在上啊。

emmm.

那就把圆心加上咯:在每条边中间加一个点。

于是半径变成了 $k$。


3. 树分治

【我靠bb了近 100 行终于到我想写的了。。。

因为这是我第 $3$ 次写树分治,所以这篇题解主要是为了试着把树分治部分说清楚。

那么树分治具体该怎么做呢?

首先我们可以考虑,每次分治时,记录 $cnt_i$ 表示深度为 $i$ 的节点数量(根节点深度为 $1$)。

那么根节点的答案加上 $\sum_{i=1}^{k}{cnt_i}$。

对于其他节点,答案加上 $\sum_{i=1}^{k-dep_i+1}{cnt_i}$。

但是同一子树内的重复计算了,所以要减去。

void dfs(int u,int fa,int f,int x){
    if(f)ans[u]+=x*sum(cnt+1,cnt+k-d[u]+1);else cnt[d[u]]+=x;
    for(int i=h[u],v=e[i].v;i;i=e[i].nt,v=e[i].v)if(...)dfs(v,u,f);
}
void sl(int u){
    ...
    dfs(u,0,0,1);dfs(u,0,1,1);dfs(u,0,0,-1);//更新cnt,更新答案,清空cnt。
    ...
    for(int i=h[u],v=e[i].v;i;i=e[i].nt,v=e[i].v)if(...)
        dfs(v,u,0,1),dfs(v,u,1,-1),dfs(v,u,0,-1);
    ...
}

以上代码是我瞎写的,详情请参考最后给的代码。

但是这样做有一个很大的问题,我们可以来算一下时间复杂度。

$\mathrm O($ 树分治 $(n\times\log{n})\times \text{cnt}$ 更新答案 $(k))$

这样搞稳定 $\text{TLE}$。

可以发现这就是简单的前缀和,

  1. 使用前缀和优化,时间复杂度:$\mathrm O (n\times\log{n}+\sum{maxdep\ in\ each\ subtree}\times \log{n})$
  2. 使用 $\text{BIT}$ 优化,时间复杂度:$\mathrm O (n\times\log{n}\times\log{k})$【我失智了用的方法。。。

显然,法一比法二跟优秀,因为 $\sum{maxdep}$ 一定是 $\le n$ 的,所以它的复杂度比法二少个 $\log$。

最后统计答案时,注意根据 $k$ 的奇偶性分类讨论。


代码

/*"-Aria on the Planets-"*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double D;
typedef pair<int,int> Pii;
#define mp(a,b) make_pair(a,b)
#define fir first
#define sec second
inline int min(int _a,int _b){return _a<_b?_a:_b;}
inline int max(int _a,int _b){return _a>_b?_a:_b;}
template<class _T>inline void rd(_T &_a){int _f=0,_ch=getchar();_a=0;while(_ch<'0'||_ch>'9'){if(_ch=='-')_f=1;_ch=getchar();}while(_ch>='0'&&_ch<='9')_a=(_a<<1)+(_a<<3)+_ch-'0',_ch=getchar();if(_f)_a=-_a;}
const int inf=0x3f3f3f3f;
const D eps=1e-8;
const int N=2e5+5;
struct node{int v,nt;}e[N<<1];
int n,k,t[N],h[N],d[N],sz[N],ec,vis[N],r[N],st[N],en,rt,s,mrt,dep,x;
void add(int u,int v){e[++ec]=(node){v,h[u]};h[u]=ec;e[++ec]=(node){u,h[v]};h[v]=ec;}
void grt(int u,int fa){int mx=0;sz[u]=1;for(int i=h[u],v=e[i].v;i;i=e[i].nt,v=e[i].v)if(v!=fa&&!vis[v])grt(v,u),sz[u]+=sz[v],mx=max(mx,sz[v]);mx=max(mx,s-sz[u]);if(mx<mrt)rt=u,mrt=mx;}
void dfs(int u,int fa){st[en++]=u;d[u]=d[fa]+1;dep=max(dep,d[u]);if(u<=n)t[d[u]]+=x;if(d[u]>=k)return;for(int i=h[u],v=e[i].v;i;i=e[i].nt,v=e[i].v)if(v!=fa&&!vis[v])dfs(v,u);}
void cal(int u){en=dep=0;d[0]=x<0;dfs(u,0);for(int i=1;i<=dep;i++)t[i]+=t[i-1];for(int i=0;i<en;i++)r[st[i]]+=t[min(dep,k-d[st[i]]+1)];memset(t,0,dep+1<<2);}
void sl(int u){s=sz[u];mrt=inf;grt(u,0);u=rt;vis[u]=1;x=1;cal(u);for(int i=h[u],v=e[i].v;i;i=e[i].nt,v=e[i].v)if(!vis[v])x=-1,cal(v),sl(v);}
int main(){
    //clock_t start=clock();
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    int ans=0;rd(n);rd(k);if(k<=2||k==n){printf("%d",k);return 0;}
    for(int i=1,u,v;i<n;i++)rd(u),rd(v),add(u,i+n),add(v,i+n);
    sz[1]=n+n-1;sl(1);for(int f=(!(k&1))*n,i=1+f;i<=n+f;i++)ans=max(ans,r[i]);printf("%d",ans);
    //printf("\n%dms",(int)((D)(clock()-start)/CLOCKS_PER_SEC*1000));
    return 0;
}