[DS记录]P4220 [WC2018]通道
command_block
·
·
个人记录
题意 : 给出三颗树 T1,T2,T3 ,边有边权(非负)。
求一个点对 (a,b) 使得 T1.dis(a,b)+T2.dis(a,b)+T3.dis(a,b) 最大。
------------
两棵树的类似问题 : [P4565 [CTSC2018]暴力写挂](https://www.luogu.com.cn/problem/P4565)
- **做法一** : 边分治+虚树+维护点集直径
- 第一棵树 : 在其上边分治,考虑两部分的贡献。
将两部分分别染成黑色白色。
有 $cost=dep1[u]+dep1[v]+Len$ .现在就是给每个点加权,变为两棵树的情况。
由于是最大化,边分治的虚边虚点不会影响答案,可以随意处理,尽量减小常数。
- 第二棵树 : 建立虚树,树形 `DP `,枚举 `LCA` 计算子树内贡献。
$cost=dep1[u]+dep2[u]+dep1[v]+dep2[v]-2*dep2[lca]$. ( $u,v$ 不同色)
如果不考虑第三棵树,这就是个憨逼子树$\max$问题。
- 第三棵树 : 维护点集直径
对于第二棵树虚树上的某个 $lca$ ,有
$cost=dep1[u]+dep2[u]+dep3[u]+dep1[v]+dep2[v]+dep3[u]-dep3[lca(u,v)]$ ( $u,v$ 不同色)
由于边权非负,直径集合是封闭的,合并的时候大力分类讨论讨论即可。
这里要求能够贡献的点对异色,那么需要分别维护黑色白色两种直径,然后在之间贡献。
为了方便,可以把点权改为 $dep1[u]+dep2[u]+dep3[u]$ ,也可以理解为深度。
注意,如果一开始不使用边分治而使用点分治,这里就不能维护双色直径而维护多色直径,会导致复杂度退化。
边分治造成的虚树问题规模是 $O(n\log n)$ 的,所以朴素建虚树的复杂度是 $O(n\log^2n)$.
树形`DP`时需要(较大常数) $O(n\log n)$ 次求$T3$上路径长度。
建议使用较快的树剖`LCA`.总复杂度 $O(n\log^2 n)$。
```cpp
```
- **做法二** : 边分树合并+维护点集直径
给第一颗树建立边分树,维护第二棵树上的点集直径,在第三棵树上合并边分树。
在第三棵树上 `dfs` 时, $lca3(u,v)$ 已经确定了,不需要再考虑。
对于边分树的每一层,可以把点权改为 $dep1[u]+dep2[u]+dep3[u]$ (注意不同层 $dep1$ 的意义不同),在该层合并直径。
这样,会有 $O(n\log n)$ 次直径合并,其余的复杂度都是 $O(n\log n)$ 的,若采用 $O(1)$ `LCA` ,则可以做到严格 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define INF (1ll<<60)
#define MaxN 100500
#define MaxT 200500
#define forG(u) for (int i=fir[u],v;i;i=g[i].nxt)
using namespace std;
inline int read(){
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
inline ll readll(){
ll X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
struct Line
{int t,nxt;ll l;}g[MaxT<<1];
int tl=1,fir[MaxT];
void adl(int f,int t,ll len){
g[++tl]=(Line){t,fir[f],len};fir[f]=tl;
g[++tl]=(Line){f,fir[t],len};fir[t]=tl;
}
int tot,st[MaxT],siz[MaxT],ms[MaxT],e[MaxT],ef;
void clear(int n)
{for (int i=1;i<=n;i++)e[i]=fir[i]=0;tl=1;}
void pfs(int u){
e[u]=ef;siz[st[++tot]=u]=1;
forG(u) if (e[v=g[i].t]<ef)
{pfs(v);siz[u]+=siz[v];}
}
int grt(int u)
{
tot=0;ef++;pfs(u);
int rt=0;
for (int i=1;i<=tot;i++){
ms[st[i]]=max(siz[st[i]],tot-siz[st[i]]);
if (ms[st[i]]<=ms[rt])rt=st[i];
}return rt;
}
struct TrNode
{int f;bool tr;}b[MaxT<<1];
int tn2;
ll d[32][MaxT],*dis;
void dfs(int u){
e[u]=ef;
forG(u) if (e[v=g[i].t]<ef)
{dis[v]=dis[u]+g[i].l;dfs(v);}
}
int solve(int u,int dep)
{
int v,tp=0;
for (int i=fir[u];i;i=g[i].nxt)
if (siz[g[i].t]>siz[u])
{v=g[tp=i].t;break;}
if (!tp)return u;
dis=d[dep];ef++;dfs(u);
g[tp].t=g[tp^1].t=0;
int pos=++tn2;
b[u=solve(grt(u),dep+1)].tr=0;b[u].f=pos;
b[v=solve(grt(v),dep+1)].tr=1;b[v].f=pos;
return pos;
}
struct SLine
{int f,t;ll l;}sl[MaxN];
int las[MaxN],tn3;
void cre(int u,int v,ll len){
if (siz[v]>siz[u])swap(u,v);
if (!las[u]){las[u]=u;adl(u,v,len);}
else {
adl(++tn3,las[u],0);
adl(las[u]=tn3,v,len);
}
}
struct ST
{
int tim,in[MaxN],dep[MaxN],lg2[MaxN<<1],c[19][MaxN<<1];
void dfs(int u)
{
e[u]=1;
c[0][in[u]=++tim]=u;
forG(u) if (!e[v=g[i].t]){
dep[v]=dep[u]+1;
dfs(v);
c[0][++tim]=u;
}
}
inline int minp(int x,int y)
{return dep[x]<dep[y] ? x:y;}
void Init()
{
dfs(1);
for (int i=2;i<=tim;i++)lg2[i]=lg2[i>>1]+1;
for (int j=0;(1<<(j+1))<=tim;j++)
for (int i=1;i+(1<<j)<=tim;i++)
c[j+1][i]=minp(c[j][i],c[j][i+(1<<j)]);
}
int lca(int l,int r){
if (!l||!r)return 0;
l=in[l];r=in[r];if (l>r)swap(l,r);
int t=lg2[r-l+1];
return minp(c[t][l],c[t][r-(1<<t)+1]);
}
}T;
ll dep2[MaxN],dep3[MaxN],w[MaxN];
struct PLine{int f,t;};
struct Node
{int l,r;PLine x;}a[MaxN*32];
int tn,rt[MaxN];
int build(const int u)
{
int p=u;
while(1){
a[++tn].x=(PLine){u,u};
if (!b[p].f)break;
if (b[p].tr)a[tn+1].r=tn;
else a[tn+1].l=tn;
p=b[p].f;
}return tn;
}
inline ll gdis(const int u,const int v)
{return dis[u]+w[u]+dis[v]+w[v]-2*dep2[T.lca(u,v)];}
ll ans=-INF;
ll calc(const PLine &A,const PLine &B)
{return max(max(gdis(A.f,B.f),gdis(A.f,B.t)),max(gdis(A.t,B.f),gdis(A.t,B.t)));}
PLine Pmerge(const PLine &A,const PLine &B)
{
PLine ret;ll mx=-INF,sav;
if ((sav=gdis(A.f,A.t))>mx){mx=sav;ret=A;}
if ((sav=gdis(B.f,B.t))>mx){mx=sav;ret=B;}
if ((sav=gdis(A.f,B.f))>mx){mx=sav;ret=(PLine){A.f,B.f};}
if ((sav=gdis(A.f,B.t))>mx){mx=sav;ret=(PLine){A.f,B.t};}
if ((sav=gdis(A.t,B.f))>mx){mx=sav;ret=(PLine){A.t,B.f};}
if ((sav=gdis(A.t,B.t))>mx){mx=sav;ret=(PLine){A.t,B.t};}
return ret;
}
int merge(int x,int y,int dep,ll buf)
{
if (!x||!y)return x|y;
if (dep){
dis=d[dep-1];
a[x].x=Pmerge(a[x].x,a[y].x);
}dis=d[dep];
if (a[x].l&&a[y].r)ans=max(ans,buf+calc(a[a[x].l].x,a[a[y].r].x));
if (a[y].l&&a[x].r)ans=max(ans,buf+calc(a[a[y].l].x,a[a[x].r].x));
a[x].l=merge(a[x].l,a[y].l,dep+1,buf);
a[x].r=merge(a[x].r,a[y].r,dep+1,buf);
return x;
}
void dfs2(int u)
{
e[u]=1;rt[u]=build(u);
forG(u) if (!e[v=g[i].t]){
dep3[v]=dep3[u]+g[i].l;
w[v]=dep2[v]+dep3[v];
dfs2(v);
rt[u]=merge(rt[u],rt[v],0,-2*dep3[u]);
}
}
int main()
{
int n=tn3=read();
for (int i=1,fr,to;i<n;i++){
fr=read();to=read();
sl[i]=(SLine){fr,to,readll()};
adl(fr,to,sl[i].l);
}ef++;pfs(1);clear(n);
for (int i=1;i<n;i++)
cre(sl[i].f,sl[i].t,sl[i].l);
tn2=tn3;
ms[0]=e[0]=(1<<30);solve(grt(1),0);
clear(tn3);
for (int i=1,fr,to;i<n;i++){
fr=read();to=read();
adl(fr,to,readll());
}T.Init();
dis=dep2;ef=2;dfs(1);
clear(n);
for (int i=1,fr,to;i<n;i++){
fr=read();to=read();
adl(fr,to,readll());
}dfs2(1);
printf("%lld",ans);
}
```