题解 P4220 【[WC2018]通道】

这题是真的毒

三棵树的题真的可以搞死你

前置芝士:快速lca

由于这道题中求lca的次数相当的多,请使用快速求lca的方式来求lca，比如st表

前置芝士:虚树

如果不知道什么是虚树的话可以做一做这三道题

P2495 [SDOI2011]消耗战

P4103 [HEOI2014]大工程

P4606 [SDOI2018]战略游戏

然后你应该就就知道这东西是用来干什么的以及它怎么写了

前置芝士:边分治

可能点分治大家都十分熟练了吧(不然估计不敢来淦这道猫式树上最优化问题)

但是其实边分治的题就比较少了,所以让我们来普及一下边分治的基本姿势

边分治的算法流程

1.多叉树转二叉树

2.找中心边

3.切掉这条中心边并且处理过中心边的所有路径

4.递归分治左右两个联通块

那么我们一步一步的讲解这些步骤该怎么做

多叉树转二叉树

可能很多人都听说过这个东西，但是并不知道这个东西具体来讲怎么写

多叉树转二叉树的策略被称为左儿子右兄弟

但是其实这个策略并不好使，因为你发现你真的按照左儿子右兄弟转完二叉树之后就会发现转化之后的树和原来的树半毛钱关系没有，甚至转化之后任意两个点间的距离这个最松的条件都变了

对，因为这个原则省略了一句话叫添加虚点

具体来讲对于多叉树转二叉树这个问题来讲我们像下面的图一样插入一些虚点，然后就可以多叉树转二叉树了

图中的红色方点全部是插入的虚点，灰色的边表示这是一条边权为0的边，黑色的边表示这是和树上原来的边权相等的边

关于具体的实现可以看我代码中Tr1::Ot这个namespace中的代码

找中心边

没啥好说的，找到一个边使得切断这条边之后最大子树尽可能的小

直接暴力dfs两遍找一下就行了

切掉中心边

有一个小问题是无向边在邻接表中是存储为两条有向边的，我们如何同时切掉这两条边呢？、

这里我们需要使用一个在网络流当中使用的trick，我们令邻接表的cnt=1并且保证一条无向边对应的两条边是相邻的,这样的话我们假设得知了其中的一条边的编号i，那么i^1就是反向边的编号了，这样我们就可以快速得知一条边对应的反向边的标号了

本题题解

那么我们发现这题是三棵树

思路很简单，一棵树换一个算法然后多套几层就出来了

首先我们对第一棵树进行边分治,这样我们可以在O(logn)层分治当中解决完所有的路径(a,b)

那么假设我们我们正在考虑经过中心边(st,ed)的所有路径,那么我们发现一个路径(a,b)经过中心边当且仅当切掉这条边之后a和st属于同一个联通块而b和ed属于同一个联通块

那么我们不妨把切掉中心边之后所有和st相连的点全部标成黑色,所有和ed相连的点全部标成白色

此时我们在这一层当中的任务就是寻找一个对点(a,b)使得

dis(a,st)+dis(ed,b)+val(st,ed)+T2.dis(a,b)+T3.dis(a,b)

最大并且a是一个黑点,b是一个白点

那么我们发现val(st,ed)似乎是一个常量我们不用管他

然后我们接着拆拆式子

dis(a,st)+dis(ed,b)+T2.dep(a)+T2.dep(b)+T3.dep(a)+T3.dep(b)

上面这些都是仅仅和a或者仅仅和b有关的数值还要加上

-2T2.dep(lca(a,b))-2T3.dep(lca(a,b))

然后我们可以很方便的处理出w(x)=dis(x,st/ed)+T2.dep(x)+T3.dep(x)

那么此时我们要最大化的式子就是

w(a)+w(b)-2T2.dep(lca(a,b))-2T3.dep(lca(a,b))

我们发现一件事，边分治出来的黑色点和白色点也是点的集合

既然是点的集合就可以跑虚树啊

所以我们把所有的黑色点和白色点放到T2上去跑虚树

那么构建出虚树之后我们可以在虚树上dfs来枚举T2.lca(a,b)的值假设我们枚举的lca是p,那么此时-2T2.dep(p)已经是一个定值我们的目标就是找到一对点(a,b)其中a和b来自p不同的子树并且a是黑点b是白点

同时最大化

w(a)+w(b)-2T3.dep((lca(a,b))

那么其实我们是可以dp来求解这个东西的

具体来讲为了做这题我们需要一个结论

对于一颗边权全部是正的树,假如说这颗树上有一个点集A的最长路端点分别是u,v 另有一个点集B的最长路端点分别是a,b,那么跨越点集A和B的最长路端点只可能是(u,a),(v,b),(u,b),(v,a)四条路径当中的一个

那么有了这个性质我们就可以设计一个树形dp/贪心

我们记dp(u,0)表示u子树中的白点这个点集在T3的最长路端点,dp(u,1)表示u子树中的黑点这个点集在T3的最长路端点

转移是显然的,贡献答案的时候在合并两个联通块的时候计算,具体来讲假如说我们需要合并dp(u)和dp(v)这两个状态,并且假设u是v的父亲

那么显然跨越这两个联通块的点对(a,b)的lca都是u了,所以我们只需要计算出跨越联通块的最长距离然后减去2T2.dep(u)就行了

跨越联通块的最长距离也十分好算,我们只需要求出跨越dp(u,0)和dp(v,1)的最长距离和跨越dp(v,1)和dp(u,0)的最长距离就行了，利用刚才的结论枚举八个点对然后求一下距离就行了

看起来我们似乎在O(nlog^2n)的时间内做完了这道题？

其实我们忽略了一个小细节

我们刚才的距离其实全部指的是这个式子，而不是T3上的实际距离

realdis(a,b)=w(a)+w(b)-2T3.dep(lca(a,b))

换句话说也指这个式子

realdis(a,b)=(dis(a,st)+T2.dep(a))+(dis(ed,b)+T2.dep(b))+T3.dis(a,b)

显然这个式子并不是T3上的树上距离，那么我们刚才的结论为什么依然对这种"距离"成立呢？

答案其实也很简单为了证明这个结论(换句话说你在代码中要做的就是把计算距离的式子改一下)我们在每个点i下新建一个虚点i'并且令i'和i之间连一条边权为(dis(i,st/ed)+T2.dep(i))的边，这样的话我们会发现

realdis(a,b)=dis(a',b')

然后我们的结论就可以接着用下去了

然后就是这题码量巨大……少数写到150行的题……

注意你的手……

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;typedef long long ll;ll ans;
int n;int lg[2*N];ll nw[N];int typ[N];int q1[N];int q2[N];int hd1;int hd2;
# define cmi(u,v) (dep[u]<dep[v]?u:v)
inline void clg(){for(int i=2,j=1;i<=2*n;i++)j=(((1<<(j+1))<=i)?j+1:j),lg[i]=j;}
namespace Tr3//第3棵树 
{
    int v[2*N];int x[2*N];int ct;int al[N];ll val[2*N];ll dis[2*N];
    int st[20][2*N];int fir[N];int dep[N];int hd;
    inline void add(int u,int V,ll va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;}
    inline void dfs(int u,int f)
    {
        st[0][++hd]=u;fir[u]=hd;nw[u]+=dis[u];
        for(int i=al[u];i;i=x[i])
            if(v[i]!=f)dis[v[i]]=dis[u]+val[i],dep[v[i]]=dep[u]+1,dfs(v[i],u),st[0][++hd]=u;
    }
    inline void prest()
    {for(int k=1,j=1;k<hd;k<<=1,j++)for(int i=1;i+k<=hd;i++)st[j][i]=cmi(st[j-1][i],st[j-1][i+k]);}
    inline int lca(int u,int v)//求lca算距离 
    {
        u=fir[u];v=fir[v];if(v<u)swap(u,v);int j=lg[v-u+1];
        int res=cmi(st[j][u],st[j][v-(1<<j)+1]);return res;
    }
    inline ll cdis(int u,int v){return nw[u]+nw[v]-(dis[lca(u,v)]<<1);}
}
namespace Tr2
{
    int v[2*N];int x[2*N];int ct;int al[N];ll val[2*N];int sta[N];int tp;
    int st[20][2*N];int fir[N];int dep[N];int hd;ll dis[N];
    bool book[N];int op[2*N];int tpop;int dfi[N];int dfo[N];int df;
    # define cd(u,v) (Tr3::cdis(u,v))
    struct data//dp用的结构体 
    {
        int u;int v;ll dis;data(){u=0;v=0;dis=0;}
        data (const int& U,const int& V){u=U;v=V;dis=cd(u,v);}
        data (const int& U,const int& V,const int& D){u=U;v=V;dis=D;}
        friend bool operator <(data a,data b){return a.dis<b.dis;}
        friend data operator +(data a,data b)
        {
            if(a.u==0)return b;if(b.u==0)return a;
            data res=max(a,b);res=max(res,max(data(a.u,b.v),data(a.v,b.u)));
            res=max(res,max(data(a.u,b.u),data(a.v,b.v)));return res;
        }
    }dp[N][2];
    inline ll mgdat(const data& a,const data& b)
    {
        if(a.u==0||b.u==0)return 0;
        return max(max(cd(a.u,b.u),cd(a.v,b.v)),max(cd(a.u,b.v),cd(a.v,b.u)));
    }
    inline void add(int u,int V,ll va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;}
    inline bool cmp(int a,int b)
    {int k1=(a<0)?dfo[-a]:dfi[a];int k2=(b<0)?dfo[-b]:dfi[b];return k1<k2;}
    inline void dfs(int u,int f)
    {
        st[0][++hd]=u;fir[u]=hd;dfi[u]=++df;nw[u]+=dis[u];
        for(int i=al[u];i;i=x[i])
            if(v[i]!=f)dis[v[i]]=dis[u]+val[i],dep[v[i]]=dep[u]+1,dfs(v[i],u),st[0][++hd]=u;
        dfo[u]=++df;
    }
    inline void prest()
    {for(int k=1,j=1;k<hd;k<<=1,j++)for(int i=1;i+k<=hd;i++)st[j][i]=cmi(st[j-1][i],st[j-1][i+k]);}
    inline int lca(int u,int v)
    {
        u=fir[u];v=fir[v];if(v<u)swap(u,v);int j=lg[v-u+1];
        return cmi(st[j][u],st[j][v-(1<<j)+1]);
    }   
    inline void solve(ll k)//建虚树并在虚树上树形dp 
    {
        tpop=0;for(int i=1;i<=hd1;i++)op[++tpop]=q1[i];
        for(int i=1;i<=hd2;i++)op[++tpop]=q2[i];sort(op+1,op+tpop+1,cmp);
        for(int i=1;i<=tpop;i++)book[op[i]]=true;
        for(int i=1;i<=tpop;i++)
            {int u=op[i],t=typ[u];dp[u][t]=data(u,u,0),dp[u][t^1]=data();}
        for(int i=1,lim=tpop;i<lim;i++)
            {int lc=lca(op[i],op[i+1]);if(!book[lc])book[lc]=true,op[++tpop]=lc,dp[lc][0]=dp[lc][1]=data();}
        for(int i=1;i<=tpop;i++)book[op[i]]=false;
        for(int i=1,lim=tpop;i<=lim;i++)op[++tpop]=-op[i];sort(op+1,op+tpop+1,cmp);
        for(int i=1;i<=tpop;i++)
            if(op[i]>0)sta[++tp]=op[i];
            else 
            {
                tp--;if(!tp)continue;int u=sta[tp+1];int f=sta[tp];
                ans=max(ans,max(mgdat(dp[u][0],dp[f][1]),mgdat(dp[u][1],dp[f][0]))+k-(dis[f]<<1));
                dp[f][0]=dp[f][0]+dp[u][0];dp[f][1]=dp[f][1]+dp[u][1];
            }   
    }
}
namespace Tr1//第一颗树 
{
    int v[4*N];int x[4*N];int ct=1;int al[2*N];ll val[4*N];int siz[2*N];
    bool cut[4*N];ll w[2*N];int res;int resv;
    inline void add(int u,int V,ll va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;}
    namespace Ot//多叉树转二叉树 
    {
        int ctt;int nu[N];int v[2*N];int x[2*N];int ct;int al[N];ll val[2*N];
        inline void add(int u,int V,ll va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;}
        inline void ins(int u,int V,ll va)
        {
            ++ctt;Tr1::add(ctt,V,va);Tr1::add(V,ctt,va);
            Tr1::add(nu[u],ctt,0);Tr1::add(ctt,nu[u],0);nu[u]=ctt;
        }
        inline void build(int u,int f)
        {for(int i=al[u];i;i=x[i])if(v[i]!=f){ins(u,v[i],val[i]);build(v[i],u);}}
        inline void cbuild(){for(int i=1;i<=n;i++)nu[i]=i;ctt=n;build(1,0);}
    }
    inline int dfs1(int u,int f)
    {siz[u]=1;for(int i=al[u];i;i=x[i])if(v[i]!=f&&!cut[i])siz[u]+=dfs1(v[i],u);return siz[u];}
    inline void find(int u,int f,const int& tot)
    {
        for(int i=al[u];i;i=x[i])
            if(v[i]!=f&&!cut[i])
            {int ky=max(siz[v[i]],tot-siz[v[i]]);if(resv>ky)resv=ky,res=i;find(v[i],u,tot);}
    }
    inline void glt(int u,int f)
    {
        if(u<=n)typ[u]=0,q1[++hd1]=u;
        for(int i=al[u];i;i=x[i])if(v[i]!=f&&!cut[i])w[v[i]]=w[u]+val[i],glt(v[i],u);
    }
    inline void grt(int u,int f)
    {
        if(u<=n)typ[u]=1,q2[++hd2]=u;
        for(int i=al[u];i;i=x[i])if(v[i]!=f&&!cut[i])w[v[i]]=w[u]+val[i],grt(v[i],u);
    }
    inline void del(int u,int f)
    {for(int i=al[u];i;i=x[i])if(v[i]!=f&&!cut[i])del(v[i],u),cut[i]=cut[i^1]=true;}
    inline void solve(int u)//边分治 
    {
        dfs1(u,0);if(siz[u]==1)return;res=0;resv=0x3f3f3f3f;find(u,0,siz[u]);
        int st=v[res];int ed=v[res^1];cut[res]=true;cut[res^1]=true;
        hd1=0;hd2=0;w[st]=w[ed]=0;glt(st,0);grt(ed,0);
        if(hd1==0||hd2==0)//小剪枝，如果联通块全部是虚点就不进行分治 
            {if(hd1==0)del(st,0),solve(ed);else del(ed,0),solve(st);return;}
        for(int i=1;i<=hd1;i++)nw[q1[i]]+=w[q1[i]];
        for(int i=1;i<=hd2;i++)nw[q2[i]]+=w[q2[i]];
        Tr2::solve(val[res]);
        for(int i=1;i<=hd1;i++)nw[q1[i]]-=w[q1[i]];
        for(int i=1;i<=hd2;i++)nw[q2[i]]-=w[q2[i]];solve(st);solve(ed);
    }
}
int main()
{
    scanf("%d",&n);clg();ll va;
    for(int i=1,u,v;i<n;i++)scanf("%d%d%lld",&u,&v,&va),Tr1::Ot::add(u,v,va),Tr1::Ot::add(v,u,va);
    for(int i=1,u,v;i<n;i++)scanf("%d%d%lld",&u,&v,&va),Tr2::add(u,v,va),Tr2::add(v,u,va);
    for(int i=1,u,v;i<n;i++)scanf("%d%d%lld",&u,&v,&va),Tr3::add(u,v,va),Tr3::add(v,u,va);
    Tr3::dfs(1,0);Tr3::prest();Tr2::dfs(1,0);Tr2::prest();Tr1::Ot::cbuild();Tr1::solve(1);
    printf("%lld",ans);return 0;//拜拜程序~ 
}