cf379F. New Year Tree

链接

点击跳转

题解

做法一(TLE)：

维护每个点到最远的儿子的距离 $dis_x$
设 $y$的左右儿子为 $a,b$，那么以 $y$为 $lca$的最长链的长度就是 $dis_a+dis_b$

每次给一个叶子挂上两个孩子，都会影响到包含这个叶子结点的一条链的 $dis$和 $f$值，拿树剖+线段树维护一下就可以了

时间复杂度 $O(nlog^2n)$

做法二(TLE)：
分析同上，拿 $lct$去维护这个东西，时间复杂度 $O(nlogn)$

都知道 $splay$常数大，所以 $T$掉也是没办法的事请

做法三(AC):

要用到一定的树的知识，直径的求法就是从任意一个点出发找到离这个点最远的点，假设这个最远的点是 $u$，那么可以证明 $u$肯定是直径的端点，再从 $u$出发找最远点 $v$，则路径 $(u,v)$就是直径

考虑新加入的点 $x$，如果新树的直径包含 $x$，那么要么是 $(u,x)$，要么是 $(v,x)$，直接更新一下就好了

代码一(TLE)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1000010
#define maxe 1000010
#define maxk 19
#define cl(x) memset(x,0,sizeof(x))
#define rep(_,__) for(_=1;_<=(__);_++)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll read(ll x=0)
{
    ll c, f(1);
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-0x30;
    return f*x;
}
struct Graph
{
    int etot, head[maxn], to[maxe], next[maxe], w[maxe];
    void clear(int N)
    {
        for(int i=1;i<=N;i++)head[i]=0;
        etot=0;
    }
    void adde(int a, int b, int c=0){to[++etot]=b;w[etot]=c;next[etot]=head[a];head[a]=etot;}
}G;
struct ShuLianPouFen
{
    int size[maxn], top[maxn], tid[maxn], tim, untid[maxn], deep[maxn], son[maxn], fa[maxn];
    void dfs1(Graph &G, int pos)
    {
        int p, v;
        size[pos]=1;
        for(p=G.head[pos];p;p=G.next[p])
        {
            if((v=G.to[p])==fa[pos])continue;
            fa[v]=pos;
            deep[v]=deep[pos]+1;
            dfs1(G,v);
            if(size[v]>size[son[pos]])son[pos]=v;
            size[pos]+=size[v];
        }
    }
    void dfs2(Graph &G, int pos, int tp)
    {
        int p, v;
        top[pos]=tp;
        tid[pos]=++tim;
        untid[tid[pos]]=pos;
        if(son[pos])dfs2(G,son[pos],tp);
        for(p=G.head[pos];p;p=G.next[p])
            if((v=G.to[p])!=fa[pos] and v!=son[pos])dfs2(G,v,v);
    }
    void run(Graph &G, int root)
    {
        tim=0;
        deep[root]=1;
        dfs1(G,root);
        dfs2(G,root,root);
    }
}sp;
struct SegmentTree
{
    #define inf 0x3f3f3f3f
    int mx[maxn<<2], add[maxn<<2], L[maxn<<2], R[maxn<<2];
    void maketag_add(int o, int v)
    {
        add[o]+=v;
        mx[o]+=v;
    }
    void pushdown(int o)
    {
        if(L[o]==R[o])return;
        if(add[o])
        {
            maketag_add(o<<1,add[o]);
            maketag_add(o<<1|1,add[o]);
            add[o]=0;
        }
    }
    void pushup(int o)
    {
        mx[o]=max(mx[o<<1],mx[o<<1|1]);
    }
    void build(int o, int l, int r)
    {
        int mid(l+r>>1);
        L[o]=l, R[o]=r;
        add[o]=0;
        if(l==r)
        {
            return;
        }
        build(o<<1,l,mid);
        build(o<<1|1,mid+1,r);
        pushup(o);
    }
    void segadd(int o, int l, int r, int v)
    {
        int mid(L[o]+R[o]>>1);
        if(l<=L[o] and r>=R[o]){maketag_add(o,v);return;}
        pushdown(o);
        if(l<=mid)segadd(o<<1,l,r,v);
        if(r>mid)segadd(o<<1|1,l,r,v);
        pushup(o);
    }
    int segmax(int o, int l, int r)
    {
        int mid(L[o]+R[o]>>1), ans(-inf);
        if(l<=L[o] and r>=R[o])return mx[o];
        pushdown(o);
        if(l<=mid)ans=max(ans,segmax(o<<1,l,r));
        if(r>mid)ans=max(ans,segmax(o<<1|1,l,r));
        return ans;
    }
    #undef inf
}dep, f;
struct Doubling_LCA
{
    int f[maxn][maxk+1], depth[maxn];
    void clear(int n){for(int i=1;i<=n;i++)depth[i]=0, cl(f[i]);}
    void dfs(Graph &G, int pos, int pre)
    {
        for(auto k=1;(1<<k)<=depth[pos];k++)f[pos][k]=f[f[pos][k-1]][k-1];
        for(auto p(G.head[pos]);p;p=G.next[p])
            if(G.to[p]!=pre)
            {
                f[G.to[p]][0]=pos;
                depth[G.to[p]]=depth[pos]+1;
                dfs(G,G.to[p],pos);
            }
    }
    void run(Graph &G, int root)
    {
        depth[root]=1;
        dfs(G,root,0);
    }
    int q(int x, int y)
    {
        if(depth[x]<depth[y])swap(x,y);
        for(auto k(maxk);~k;k--)
            if(depth[f[x][k]]>=depth[y])
                x=f[x][k];
        if(x==y)return x;
        for(auto k(maxk);~k;k--)
            if(f[x][k]!=f[y][k])
                x=f[x][k], y=f[y][k];
        return f[x][0];
    }
    int jp(int x, int b)
    {
        for(auto k=0;k<=maxk;k++)
            if(b&(1<<k))x=f[x][k];
        return x;
    }
}db;
void add(SegmentTree &t, int x, int y, int v)
{
    int tx=sp.top[x];
    while(tx!=sp.top[y])
    {
        t.segadd(1,sp.tid[tx],sp.tid[x],v);
        x=sp.fa[tx], tx=sp.top[x];
    }
    t.segadd(1,sp.tid[y],sp.tid[x],v);
}
int v[maxn];
int main()
{
    int q, n=4, i, cnt;
    q=read();
    G.adde(1,2), G.adde(1,3), G.adde(1,4);
    rep(i,q)
    {
        v[i]=read();
        G.adde(v[i],n+1);
        G.adde(v[i],n+2);
        n+=2;
    }
    sp.run(G,1);
    db.run(G,1);
    dep.build(1,1,n);
    f.build(1,1,n);
    dep.segadd(1,sp.tid[1],sp.tid[1],+2);
    dep.segadd(1,sp.tid[2],sp.tid[2],+2);
    dep.segadd(1,sp.tid[3],sp.tid[3],+2);
    dep.segadd(1,sp.tid[4],sp.tid[4],+2);
    cnt=4;
    rep(i,q)
    {
        int x=v[i];
        for(int k=maxk;~k;k--)
            if(db.f[x][k]!=0 and dep.segmax(1,sp.tid[db.f[x][k]],sp.tid[db.f[x][k]])<sp.deep[v[i]]+1)
                x=db.f[x][k];
        add(dep,v[i],x,+1);
        add(dep,cnt+1,cnt+1,+sp.deep[cnt+1]);
        add(dep,cnt+2,cnt+2,+sp.deep[cnt+2]);
        add(f,v[i],x==1?1:sp.fa[x],+1);
        add(f,v[i],v[i],+1);
        int ans=f.segmax(1,2,n);
        int d2, d3, d4;
        d2=dep.segmax(1,sp.tid[2],sp.tid[2])-1;
        d3=dep.segmax(1,sp.tid[3],sp.tid[3])-1;
        d4=dep.segmax(1,sp.tid[4],sp.tid[4])-1;
        ans=max(ans,d2+d3), ans=max(ans,d3+d4), ans=max(ans,d2+d4);
        printf("%d\n",ans);
        cnt+=2;
    }
    return 0;
}

代码二(TLE)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1000010
#define maxe 1000010
#define maxk 19
#define cl(x) memset(x,0,sizeof(x))
#define rep(_,__) for(_=1;_<=(__);_++)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll read(ll x=0)
{
    ll c, f(1);
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-0x30;
    return f*x;
}
struct Graph
{
    int etot, head[maxn], to[maxe], next[maxe], w[maxe];
    void clear(int N)
    {
        for(int i=1;i<=N;i++)head[i]=0;
        etot=0;
    }
    void adde(int a, int b, int c=0){to[++etot]=b;w[etot]=c;next[etot]=head[a];head[a]=etot;}
}G;
struct LinkCutTree
{
    int rev[maxn], f[maxn], ch[maxn][2], s[maxn], mx[maxn], add[maxn], v[maxn];
    int getwh(int x)
    {if(f[x]==0)return -1;if(ch[f[x]][0]==x)return 0;if(ch[f[x]][1]==x)return 1;return -1;}
    bool isroot(int x){return getwh(x)==-1;}
    void maketag_rev(int x){if(x)rev[x]^=1;}
    void maketag_add(int x, int v){if(x)add[x]+=v;}
    void join(int x, int y, int wh){if(x)f[x]=y;if(y)ch[y][wh]=x;}
    void pushdown(int x)
    {
        if(rev[x])
        {
            swap(ch[x][0],ch[x][1]);
            maketag_rev(ch[x][0]), maketag_rev(ch[x][1]);
            rev[x]=0;
        }
        if(add[x])
        {
            v[x]+=add[x];
            mx[x]+=add[x];
            maketag_add(ch[x][0],add[x]);
            maketag_add(ch[x][1],add[x]);
            add[x]=0;
        }
    }
    void pushup(int x)
    {
        pushdown(ch[x][0]), pushdown(ch[x][1]);
        mx[x]=v[x];
        if(ch[x][0])mx[x]=max(mx[x],mx[ch[x][0]]);
        if(ch[x][1])mx[x]=max(mx[x],mx[ch[x][1]]);
    }
    void rotate(int x)
    {
        int y=f[x], z=f[y];
        int c=getwh(x);
        if(!isroot(y))join(x,z,getwh(y));
        else f[x]=z;
        join(ch[x][!c],y,c);
        join(y,x,!c);
        pushup(y);
        pushup(x);
    }
    void splay(int x)
    {
        int y, top(0);
        for(y=x;!isroot(y);y=f[y])s[++top]=y;s[++top]=y;
        for(;top;top--)pushdown(s[top]);
        while(!isroot(x))
        {
            y=f[x];
            if(isroot(y)){rotate(x);break;}
            if(getwh(x)^getwh(y))rotate(x);
            else rotate(y);
            rotate(x);
        }
    }
    void access(int x)
    {
        int t=0;
        while(x)
        {
            splay(x);
            ch[x][1]=t;
            pushup(x);
            t=x;x=f[x];
        }
    }
    void makeroot(int x){access(x);splay(x);maketag_rev(x);}
    void link(int x, int y){makeroot(x);f[x]=y;}
    void cut(int x, int y)
    {
        makeroot(x); access(y);
        splay(y);
        if(ch[y][0]==x and ch[x][1]==0)f[x]=ch[y][0]=0;
    }
    int findroot(int x)
    {
        access(x); splay(x);
        while(ch[x][0])pushdown(x), x=ch[x][0];
        splay(x);
        return x;
    }
}f, dep;
struct Doubling_LCA
{
    int f[maxn][maxk+1], depth[maxn];
    void clear(int n){for(int i=1;i<=n;i++)depth[i]=0, cl(f[i]);}
    void dfs(Graph &G, int pos, int pre)
    {
        for(auto k=1;(1<<k)<=depth[pos];k++)f[pos][k]=f[f[pos][k-1]][k-1];
        for(auto p(G.head[pos]);p;p=G.next[p])
            if(G.to[p]!=pre)
            {
                f[G.to[p]][0]=pos;
                depth[G.to[p]]=depth[pos]+1;
                dfs(G,G.to[p],pos);
            }
    }
    void run(Graph &G, int root)
    {
        depth[root]=1;
        dfs(G,root,0);
    }
    int q(int x, int y)
    {
        if(depth[x]<depth[y])swap(x,y);
        for(auto k(maxk);~k;k--)
            if(depth[f[x][k]]>=depth[y])
                x=f[x][k];
        if(x==y)return x;
        for(auto k(maxk);~k;k--)
            if(f[x][k]!=f[y][k])
                x=f[x][k], y=f[y][k];
        return f[x][0];
    }
    int jp(int x, int b)
    {
        for(auto k=0;k<=maxk;k++)
            if(b&(1<<k))x=f[x][k];
        return x;
    }
}db;
void add(LinkCutTree &t, int x, int y, int v)
{
    t.makeroot(y);
    t.access(x);
    t.splay(x);
    t.maketag_add(x,v);
}
int qmax(LinkCutTree &t, int x, int y)
{
    t.makeroot(y);
    t.access(x);
    t.splay(x);
    return t.mx[x];
}
int v[maxn];
int main()
{
    int q, n=4, i, cnt, ans=0;
    q=read();
    G.adde(1,2), G.adde(1,3), G.adde(1,4);
    rep(i,q)
    {
        v[i]=read();
        G.adde(v[i],n+1);
        G.adde(v[i],n+2);
        n+=2;
    }
    db.run(G,1);
    for(i=2;i<=4;i++)dep.v[i]=2;
    cnt=4;
    rep(i,q)
    {
        int x=v[i];
        for(int k=maxk;~k;k--)
            if(db.f[x][k]>1)
            {
                dep.splay(db.f[x][k]);
                if(dep.v[db.f[x][k]]<db.depth[v[i]]+1)x=db.f[x][k];
            }
        add(dep,v[i],x,+1);
        add(f,v[i],db.f[x][0]==1?x:db.f[x][0],+1);
        add(f,v[i],v[i],+1);
        ans=max(ans,qmax(f,v[i],db.f[x][0]==1?x:db.f[x][0]));

        dep.link(cnt+1,v[i]); dep.v[cnt+1]=dep.mx[cnt+1]=db.depth[cnt+1];
        dep.link(cnt+2,v[i]); dep.v[cnt+2]=dep.mx[cnt+1]=db.depth[cnt+2];
        f.link(cnt+1,v[i]);
        f.link(cnt+2,v[i]);
        
        int d2, d3, d4;
        d2=qmax(dep,2,2)-1;
        d3=qmax(dep,3,3)-1;
        d4=qmax(dep,4,4)-1;
        ans=max(ans,d2+d3), ans=max(ans,d3+d4), ans=max(ans,d2+d4);
        printf("%d\n",ans);
        cnt+=2;
    }
    return 0;
}

代码三（AC）

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1000010
#define maxe 1000010
#define maxk 19
#define cl(x) memset(x,0,sizeof(x))
#define rep(_,__) for(_=1;_<=(__);_++)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll read(ll x=0)
{
    ll c, f(1);
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-0x30;
    return f*x;
}
struct Graph
{
    int etot, head[maxn], to[maxe], next[maxe], w[maxe];
    void clear(int N)
    {
        for(int i=1;i<=N;i++)head[i]=0;
        etot=0;
    }
    void adde(int a, int b, int c=0){to[++etot]=b;w[etot]=c;next[etot]=head[a];head[a]=etot;}
}G;
struct Doubling_LCA
{
    int f[maxn][maxk+1], depth[maxn];
    void clear(int n){for(int i=1;i<=n;i++)depth[i]=0, cl(f[i]);}
    void dfs(Graph &G, int pos, int pre)
    {
        for(auto k=1;(1<<k)<=depth[pos];k++)f[pos][k]=f[f[pos][k-1]][k-1];
        for(auto p(G.head[pos]);p;p=G.next[p])
            if(G.to[p]!=pre)
            {
                f[G.to[p]][0]=pos;
                depth[G.to[p]]=depth[pos]+1;
                dfs(G,G.to[p],pos);
            }
    }
    void run(Graph &G, int root)
    {
        depth[root]=1;
        dfs(G,root,0);
    }
    int q(int x, int y)
    {
        if(depth[x]<depth[y])swap(x,y);
        for(auto k(maxk);~k;k--)
            if(depth[f[x][k]]>=depth[y])
                x=f[x][k];
        if(x==y)return x;
        for(auto k(maxk);~k;k--)
            if(f[x][k]!=f[y][k])
                x=f[x][k], y=f[y][k];
        return f[x][0];
    }
    int jp(int x, int b)
    {
        for(auto k=0;k<=maxk;k++)
            if(b&(1<<k))x=f[x][k];
        return x;
    }
}db;
int v[maxn];
int qdis(int x, int y)
{
    int lca=db.q(x,y);
    return db.depth[x]+db.depth[y]-2*db.depth[lca];
}
int main()
{
    int q, n=4, i, cnt, ans=2, a, b;
    q=read();
    G.adde(1,2), G.adde(1,3), G.adde(1,4);
    rep(i,q)
    {
        v[i]=read();
        G.adde(v[i],n+1);
        G.adde(v[i],n+2);
        n+=2;
    }
    db.run(G,1);
    a=2,b=3;
    cnt=4;
    rep(i,q)
    {
        int p=qdis(a,cnt+1)>qdis(b,cnt+1)?a:b;
        if(qdis(p,cnt+1)>ans)ans=qdis(p,cnt+1), a=p, b=cnt+1;
        printf("%d\n",ans);
        cnt+=2;
    }
    return 0;
}