CF842E Nikita and game

CodeForces

Luogu

分析

有一个显然的性质:所有直径的交一定是连续的一段。

把所有直径的端点分为两类:在连续段左边的、在连续段右边的。

第一类点存到 $S_1$ 里,第二类点存到 $S_2$ 里。

假设现在加入了一个点 $u$ 。

设加入 $u$ 之前的直径为 $maxd$ , $u$ 到 $S_1$ 中任意一点的距离为 $d_1$ ,到 $S_2$ 中任意一点的距离为 $d_2$ 。

然后分类讨论一下:

  • 如果 $\max(d_1,d_2)>maxd$ 的话:

    • 如果 $\max(d_1,d_2)=d_1$,显然 $S_2$ 变为了 $\{u\}$ 。另外还要遍历一下原 $S_2$ 中的元素 $v$ ,如果 $dis(u,v)=d_1$ 的话就要把 $v$ 丢到 $S_1$ 里去。
    • 否则类似。
  • 如果 $\max(d_1,d_2)=maxd$ 的话:

    • 如果 $\max(d_1,d_2)=d_1$ ,直接把 $u$ 加到 $S_2$ 里去即可。
    • 否则直接把 $u$ 加到 $S_1$ 里去即可。

然后答案就是 $S_1$ 的大小加 $S_2$ 的大小。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

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

const int N=300000+10;

int dep[N],f[20][N];

inline void add(int u,int fa) {
    dep[u]=dep[fa]+1,f[0][u]=fa;
    for (re int i=1;i<=19;++i) f[i][u]=f[i-1][f[i-1][u]];
}

inline int getlca(int u,int v) {
    if (dep[u]<dep[v]) swap(u,v);
    for (re int i=19;~i;--i)
        if (dep[f[i][u]]>dep[v]) u=f[i][u];
    if (dep[u]!=dep[v]) u=f[0][u];
    for (re int i=19;~i;--i)
        if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
    if (u!=v) u=f[0][u];
    return u;
}

inline int getdis(int u,int v) {
    int t=getlca(u,v);
    return dep[u]+dep[v]-(dep[t]<<1);
}

vector<int> S1,S2;

int main() {
    int n=read(),maxd=0; add(1,0),S1.push_back(1);
    for (re int i=1;i<=n;++i) {
        int u=i+1; add(u,read());
        int d1=S1.empty()?0:getdis(u,S1[0]);
        int d2=S2.empty()?0:getdis(u,S2[0]);
        if (max(d1,d2)>maxd) {
            maxd=max(d1,d2);
            if (d1>d2) {
                for (re int v:S2)
                    if (getdis(u,v)==d1) S1.push_back(v);
                S2={u};
            } else {
                for (re int v:S1)
                    if (getdis(u,v)==d2) S2.push_back(v);
                S1={u};
            }
        }
        else if (max(d1,d2)==maxd) {
            if (d1>d2) S2.push_back(u);
            else S1.push_back(u);
        }
        printf("%d\n",S1.size()+S2.size());
    }
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 30 PM

发表评论