题解 [JOI 2019 Final] 独特的城市

题面

解析

首先有一个结论,

对一个点\(x\)有贡献的城市

肯定在它到离它较远的直径的端点的链上.

假设离它较远的端点是\(S\),

如果有一个点\(u\)不在\(x\)到\(S\)的链上,

却对\(x\)有贡献,

那就说明\(x\)到\(u\)的距离比\(x\)到\(S\)要长,

但根据直径的定义,这是不可能的.

接下来就要考虑怎么算答案了.

首先找出直径的两个端点,

分别作为根统计一次.

维护一个栈,栈里面是可能对\(x\)有贡献的点.

然后考虑长链剖分,求出长链和次长链.

那么对于重儿子来说,栈里面的离\(x\)的距离小于等于次长链的长度的点肯定就要弹掉.

因为对重儿子没有贡献,

然后就去统计重儿子答案.

再把离\(x\)距离小于等于长链的长度的点弹掉,

剩下的就是有贡献的点了.

统计的话我们可以维护一个全局的桶,

在进栈和出栈时统计一下.

最后去统计轻儿子就行了.

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
using namespace std;

inline int read(){
    int sum=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return f*sum;
}

const int N=1000005;
struct edge{int to,next;}e[N];
int n,m,a[N],S,T,maxn;
int dep[N],len[N],son[N],sson[N];
int t[N],ans[N],now;
int sta[N],top;
int head[N],cnt;

inline void add(int x,int y){
    e[++cnt]=(edge){head[x],y};head[x]=cnt;
}

inline void dfs(int x,int fa,int dep){
    dep++;if(dep>maxn) S=x,maxn=dep;
    for(int i=head[x];i;i=e[i].to){
        int k=e[i].next;
        if(k==fa) continue;
        dfs(k,x,dep);
    }
}

inline void pre(int x,int fa){
    dep[x]=dep[fa]+1;len[x]=1;
    son[x]=sson[x]=0;
    for(int i=head[x];i;i=e[i].to){
        int k=e[i].next;
        if(k==fa) continue;
        pre(k,x);
        if(len[k]>len[son[x]]) sson[x]=son[x],son[x]=k,len[x]=len[k]+1;
        else if(len[k]>len[sson[x]]) sson[x]=k;
    }
}

inline void add(int x){
    t[a[x]]++;
    if(t[a[x]]==1) now++;
}

inline void del(int x){
    t[a[x]]--;
    if(!t[a[x]]) now--;
}

inline void dfs2(int x,int fa){
    while(top&&dep[x]-dep[sta[top]]<=len[sson[x]]) del(sta[top--]);
    sta[++top]=x;add(x);
    if(son[x]) dfs2(son[x],x);
    while(top&&dep[x]-dep[sta[top]]<=len[son[x]]) del(sta[top--]);
    ans[x]=max(ans[x],now);
    for(int i=head[x];i;i=e[i].to){
        int k=e[i].next;
        if(k==fa||k==son[x]) continue;
        if(sta[top]!=x) sta[++top]=x,add(x);
        dfs2(k,x);
    }
    if(sta[top]==x) top--,del(x);
}

signed main(){
    n=read();m=read();
    for(int i=1;i<n;i++){int x=read(),y=read();add(x,y);add(y,x);}
    for(int i=1;i<=n;i++) a[i]=read();
    dfs(1,0,0);
    T=S;S=maxn=0;
    dfs(T,0,0);
    pre(S,0);
    dfs2(S,0);
    pre(T,0);
    dfs2(T,0);
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

题解 [JOI 2019 Final] 独特的城市

原文：https://www.cnblogs.com/zsq259/p/11743872.html