uoj#347. 【WC2018】通道 | miaom's Blog
miaom's Blog

lych真的0

miaom's avatar miaom

uoj#347. 【WC2018】通道

题目大意

你有三棵树,有$n$个节点,边有非负边权,找到一对$x$,$y$,使得三棵树上$x$,$y$距离和最大。

$n\le 100000$

题解

有一个爬山的水过的方法。貌似能在考场上A的只有这个做法了。。毕竟另一种难写多了。

算法一

考虑分治第一棵树,建立虚树之后,问题转变为两棵树上选择不同颜色的两点。

可以继续分治,问题转变为一棵树,每个点有两个颜色,求两个颜色都不同的最远点对。可以dp,记录子树最深点,和最深点一个颜色不同/颜色都不同的最深点。。。复杂度$O(n\log^2n)$或$O(n\log^3n)$。

如果使用边分治,则只有两种颜色,可能比较好写?

考场上想的是这个做法,写到第一个虚树的时候放弃了。。

算法二

这个是出题人的算法。

边分治第一棵树,建立虚树。第二棵树上dfs,记录子树中每种颜色的最远点对(在第三棵树的距离加这两个点在第二棵树的深度加到分治重心的距离)。由于在两个点集中各选一点的距离的最大值的方案中,选择点的肯定是每个点集最远点对中的一点,可以容易维护答案与这个最远点对。复杂度好像是$O(n\log n)$或$O(n\log^2n)$。反正这个虚树是能线性构造的吧。。

实现

#include<bits/stdc++.h>
#define N 200005
#define ll long long
using namespace std;
int n;ll Ans;
struct edge
{
    int fst[N],nxt[N*2],to[N*2],l=1;ll len[N*2];
    void link(int x,int y,ll z)
    {
        to[++l]=y;nxt[l]=fst[x];fst[x]=l;len[l]=z;
        to[++l]=x;nxt[l]=fst[y];fst[y]=l;len[l]=z;
    }
}a,b,c,d;
struct rmq
{
    int fa[N],st[N*2],cnt,pos[N],s[25][N*2],lg[N*2],d[N];ll dep[N];

    void dfs(int x,edge &a)
    {
        st[pos[x]=++cnt]=x;
        for (int i=a.fst[x];i;i=a.nxt[i])
            if (a.to[i]!=fa[x])
            {
                fa[a.to[i]]=x;
                dep[a.to[i]]=dep[x]+a.len[i];
                d[a.to[i]]=d[x]+1;
                dfs(a.to[i],a);
                st[++cnt]=x;
            }
    }
    #define MAX(x,y) ((d[x]<d[y])?(x):(y))
    void build(edge &a)
    {
        dfs(1,a);
        lg[0]=-1;
        for (int i=1;i<=cnt;i++)
            s[0][i]=st[i],lg[i]=lg[i/2]+1;
        for (int i=1,t=1;t<=cnt;t<<=1,i++)
            for (int j=1;j+t*2-1<=cnt;j++)
                s[i][j]=MAX(s[i-1][j],s[i-1][j+t]);
    }
    int lca(int x,int y)
    {
        x=pos[x];y=pos[y];
        if (x>y) swap(x,y);
        int len=y-x+1,t=lg[len];
        return MAX(s[t][x],s[t][y-(1<<t)+1]);
    }
    ll dis(int x,int y)
    {
        return dep[x]+dep[y]-2*dep[lca(x,y)];
    }
}rmq_b,rmq_c;
int cnt;
void trans(int x,int f)
{
    int tmp=x;
    for (int i=a.fst[x];i;i=a.nxt[i])
        if (a.to[i]!=f)
        {
            d.link(tmp,++cnt,0);
            d.link(tmp=cnt,a.to[i],a.len[i]);
            trans(a.to[i],x);
        }
}
int sz[N],fa[N],Mx[N],usd[N*2];
void dfs(int x)
{
    sz[x]=x<=n;
    for (int i=d.fst[x];i;i=d.nxt[i])
        if (d.to[i]!=fa[x]&&!usd[i])
        {
            fa[d.to[i]]=x;
            dfs(d.to[i]);
            sz[x]+=sz[d.to[i]];
        }
}
void dfs(int x,int y,int &G)
{
    Mx[x]=max(sz[x],y-sz[x]);
    if (Mx[x]<Mx[G])G=x;
    for (int i=d.fst[x];i;i=d.nxt[i])
        if (d.to[i]!=fa[x]&&!usd[i])
            dfs(d.to[i],y,G);
}
int w[N],ly,col[N];ll val[N];
void Dfs(int x,int f,int c)
{
    if (x<=n)
    {
        w[++ly]=x;
        col[x]=c;
    }
    for (int i=d.fst[x];i;i=d.nxt[i])
        if (!usd[i]&&d.to[i]!=f)
        {
            val[d.to[i]]=val[x]+d.len[i];
            Dfs(d.to[i],x,c);
        }
}
int st[N],tmp[N],CNT;
int fst[N],nxt[N],to[N],l;
ll dis(int x,int y)
{
    if (!x||!y) return -1;
    return rmq_c.dis(x,y)+rmq_b.dep[x]+rmq_b.dep[y]+val[x]+val[y];
}
struct T
{
    int u[3],v[3];
};
void upd(ll x)
{
    Ans=max(Ans,x);
}
void upd(int &x,int &y,int u,int v)
{
    if (dis(x,y)<dis(u,v)) x=u,y=v;
}
T work(int x)
{
    T a=(T){{0,0,0},{0,0,0}};
    if (col[x])
        a.u[col[x]]=a.v[col[x]]=x;
    for (int i=fst[x];i;i=nxt[i])
    {
        T b=work(to[i]);
        upd(dis(a.u[1],b.u[2])-2*rmq_b.dep[x]);
        upd(dis(a.u[1],b.v[2])-2*rmq_b.dep[x]);
        upd(dis(a.v[1],b.u[2])-2*rmq_b.dep[x]);
        upd(dis(a.v[1],b.v[2])-2*rmq_b.dep[x]);
        upd(dis(a.u[2],b.u[1])-2*rmq_b.dep[x]);
        upd(dis(a.u[2],b.v[1])-2*rmq_b.dep[x]);
        upd(dis(a.v[2],b.u[1])-2*rmq_b.dep[x]);
        upd(dis(a.v[2],b.v[1])-2*rmq_b.dep[x]);
        T c=(T){{0,0,0},{0,0,0}};
        upd(c.u[1],c.v[1],a.u[1],a.v[1]);
        upd(c.u[1],c.v[1],b.u[1],b.v[1]);
        upd(c.u[1],c.v[1],a.u[1],b.u[1]);
        upd(c.u[1],c.v[1],a.u[1],b.v[1]);
        upd(c.u[1],c.v[1],a.v[1],b.u[1]);
        upd(c.u[1],c.v[1],a.v[1],b.v[1]);

        upd(c.u[2],c.v[2],a.u[2],a.v[2]);
        upd(c.u[2],c.v[2],b.u[2],b.v[2]);
        upd(c.u[2],c.v[2],a.u[2],b.u[2]);
        upd(c.u[2],c.v[2],a.u[2],b.v[2]);
        upd(c.u[2],c.v[2],a.v[2],b.u[2]);
        upd(c.u[2],c.v[2],a.v[2],b.v[2]);
        a=c;
    }
    return a;
}
void Link(int x,int y)
{
    tmp[++CNT]=x;
    to[++l]=y;nxt[l]=fst[x];fst[x]=l;
}
int lca(int x,int y)
{
    return rmq_b.lca(x,y);
}
bool cmp(int x,int y)
{
    return rmq_b.pos[x]<rmq_b.pos[y];
}
void solve(int x)
{
    int G=x;fa[x]=0;
    dfs(x);
    if (sz[x]<=1) return;
    dfs(x,sz[x],G);
    int S=fa[G];ll wzf=0;
    for (int i=d.fst[G];i;i=d.nxt[i])
        if (d.to[i]==S) wzf=d.len[i],usd[i]=usd[i^1]=1;
    ly=0;CNT=0;
    val[S]=0;val[G]=wzf;
    Dfs(S,0,1);
    Dfs(G,0,2);
    sort(w+1,w+ly+1,cmp);
    int top=1;st[1]=w[1];
    for (int i=2;i<=ly;i++)
    {
        int t=lca(w[i],st[top]);
        while(top>0&&rmq_b.d[st[top]]>rmq_b.d[t])
        {
            if (top>1&&rmq_b.d[st[top-1]]>=rmq_b.d[t])
                Link(st[top-1],st[top]);
            else Link(t,st[top]);
            top--;
        }
        if (!top||st[top]!=t) st[++top]=t;
        if (!top||st[top]!=w[i]) st[++top]=w[i];
    }
    while(top>1) Link(st[top-1],st[top]),top--;
    work(st[top]);
    for (int i=1;i<=CNT;i++)
        fst[tmp[i]]=0;
    for (int i=1;i<=ly;i++)
        col[w[i]]=0;
    l=0;
    solve(S);solve(G);
}
int main()
{
    scanf("%d",&n);
    int x,y;ll z;
    for (int i=1;i<n;i++)
        scanf("%d%d%lld",&x,&y,&z),a.link(x,y,z);
    for (int i=1;i<n;i++)
        scanf("%d%d%lld",&x,&y,&z),b.link(x,y,z);
    for (int i=1;i<n;i++)
        scanf("%d%d%lld",&x,&y,&z),c.link(x,y,z);
    rmq_b.build(b);
    rmq_c.build(c);
    cnt=n;
    trans(1,0);
    solve(1);
    printf("%lld\n",Ans);
}