卧薪尝胆，厚积薄发。
WC2018 通道
Date: Sat Jan 19 11:04:52 CST 2019
In Category:
Description：
给三棵树，求：
$$
\max_{i,j}(d_1(i,j)+d_2(i,j)+d_3(i,j))
$$
$1\leqslant n\leqslant 10^5$
Solution：
首先对
$T_1$
进行边分治，把当前分治的左右两边分别染成黑色和白色然后放在一起拿到
$T_2$
上建虚树，然后我们要最大化这样一个式子：(
$st,ed$
表示分治边的两个端点)
$$
d_1(u,st)+d_2(ed,v)+e_1(st,ed).l+dep_2[u]+dep_2[v]-2\times dep_2[LCA_2(u,v)]+d_3(u,v)
$$
$e_1(st,ed).l$
是常量不用管，那么我们可以在
$T_2$
上
$dfs$
枚举
$LCA_2(u,v)$
，然后问题就变成了找两个点
$u$
和
$v$
，他们分别来自
$T_2$
当前这个点的不同子树，并且它们的颜色是一黑一白，最大化：
$$
d_1(u,st)+d_2(ed,v)+dep_2[u]+dep_2[v]+d_3(u,v)
$$
设
$w[k]=d_1(k,st/ed)+dep_2[k]$
，那么也就是最大化：
$$
w[u]+w[v]+d_3(u,v)
$$
在树上，有一个结论就是把两棵树通过加一条边拼成一棵新树，新树的直径的端点一定也是原来两棵树的直径的四个端点之二，然后还有一个结论就是如果还要加上点权，就像上面那样，这个结论也是成立的，理解起来的话可以看成是在原来树上建一个虚点，因此我们可以设
$dp(i,0)$
（一个
$pair$
）表示在第二棵树的虚树上以
$i$
为根的子树白点的直径端点，同理
$dp(i,1)$
是黑点的，然后这样就可以
$O(1)$
合并
$dp$
数组，统计答案的话要求这两个点必须来自不同的子树，就是在第一个里取一个在第二个里取一个，然后这题就做完了。
注意边分治三度化新建的点和虚树
$LCA$
的点不应该计算。
Code：
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
using namespace std;
typedef long long ll;
#define R register
#define I inline
I ll rd()
{
R ll res = 0;R char c = getchar();
while(!isdigit(c))c = getchar();
while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();
return res;
}
int n;
#define MAXN 400010
#define INFLL 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
namespace T3
{
struct edge{int to,nxt;ll v;}e[MAXN << 1];
int edgenum = 0,lin[MAXN] = {0};
I void add(int a,int b,ll c)
{
e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;
e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;
return;
}
int dep[MAXN];
ll dist[MAXN];
int inp[MAXN],tot = 0;
int f[MAXN << 1][19];
void dfs(int k,int fa)
{
inp[k] = ++tot;f[tot][0] = k;
dep[k] = dep[fa] + 1;
for(int i = lin[k];i != 0;i = e[i].nxt)
{
if(e[i].to == fa)continue;
dist[e[i].to] = dist[k] + e[i].v;
dfs(e[i].to,k);
f[++tot][0] = k;
}
return;
}
int lg[MAXN << 1];
int mymin(int a,int b){return (dep[a] < dep[b] ? a : b);}
int LCA(int a,int b)
{
int p1 = inp[a],p2 = inp[b];if(p1 > p2)swap(p1,p2);
int l = lg[p2 - p1 + 1];
return mymin(f[p1][l],f[p2 - (1 << l) + 1][l]);
}
void build()
{
dfs(1,0);
for(int i = 2;i <= tot;++i)lg[i] = lg[i >> 1] + 1;
for(int k = 1,l = 1;k <= 18;++k,l = l << 1)
for(int i = 1;i <= tot - l + 1;++i)
f[i][k] = mymin(f[i][k - 1],f[i + l][k - 1]);
return;
}
ll dis(int a,int b){return dist[a] + dist[b] - 2 * dist[LCA(a,b)];}
ll dis(pair<int,int> a){return dis(a.first,a.second);}
}
namespace VT
{
struct edge
{
int to,nxt;
}e[MAXN << 1];
int edgenum = 0;
int lin[MAXN] = {0};
void add(int a,int b)
{
e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;
return;
}
#define fi first
#define se second
ll w1[MAXN],w2[MAXN];
ll dist[MAXN];
#define pii pair<int,int>
#define mp make_pair
pii f[MAXN][2];
ll ans = 0;
bool tag[MAXN];
int col[MAXN];
ll lenth(int a,int b){return w1[a] + w1[b] + w2[a] + w2[b] + T3::dis(a,b);}
ll calc(pii a,pii b)
{
if(a.fi == 0 || b.fi == 0)return -INFLL;
ll res = 0;
res = max(res,lenth(a.fi,b.fi));
res = max(res,lenth(a.fi,b.se));
res = max(res,lenth(a.se,b.fi));
res = max(res,lenth(a.se,b.se));
return res;
}
pii merge(pii a,pii b)
{
if(a.fi == 0)return b;if(b.fi == 0)return a;
pii res;ll val = 0;
if(lenth(a.fi,a.se) > val)res = mp(a.fi,a.se),val = lenth(a.fi,a.se);
if(lenth(b.fi,b.se) > val)res = mp(b.fi,b.se),val = lenth(b.fi,b.se);
if(lenth(a.fi,b.fi) > val)res = mp(a.fi,b.fi),val = lenth(a.fi,b.fi);
if(lenth(a.fi,b.se) > val)res = mp(a.fi,b.se),val = lenth(a.fi,b.se);
if(lenth(a.se,b.fi) > val)res = mp(a.se,b.fi),val = lenth(a.se,b.fi);
if(lenth(a.se,b.se) > val)res = mp(a.se,b.se),val = lenth(a.se,b.se);
return res;
}
ll dp(int k)
{
memset(f[k],0,sizeof(f[k]));
if(tag[k])f[k][col[k]].fi = f[k][col[k]].se = k;
ll res = 0;
for(int i = lin[k];i != 0;i = e[i].nxt)
{
res = max(res,dp(e[i].to));
res = max(res,max(calc(f[k][0],f[e[i].to][1]),calc(f[k][1],f[e[i].to][0])) - 2 * dist[k]);
f[k][0] = merge(f[k][0],f[e[i].to][0]);
f[k][1] = merge(f[k][1],f[e[i].to][1]);
}
lin[k] = 0;
return res;
}
}
namespace T2
{
struct edge{int to,nxt;ll v;}e[MAXN << 1];
int edgenum = 0,lin[MAXN] = {0};
I void add(int a,int b,ll c)
{
e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;
e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;
return;
}
int inp[MAXN],tot = 0;
int f[MAXN << 1][19];
int dep[MAXN];
ll dist[MAXN];
void dfs(int k,int fa)
{
inp[k] = ++tot;f[tot][0] = k;
dep[k] = dep[fa] + 1;
for(int i = lin[k];i != 0;i = e[i].nxt)
{
if(e[i].to == fa)continue;
dist[e[i].to] = dist[k] + e[i].v;
dfs(e[i].to,k);
f[++tot][0] = k;
}
return;
}
int lg[MAXN << 1];
int mymin(int a,int b){return (dep[a] < dep[b] ? a : b);}
int LCA(int a,int b)
{
int p1 = inp[a],p2 = inp[b];if(p1 > p2)swap(p1,p2);
int l = lg[p2 - p1 + 1];
return mymin(f[p1][l],f[p2 - (1 << l) + 1][l]);
}
void build()
{
dfs(1,0);
for(int i = 2;i <= tot;++i)lg[i] = lg[i >> 1] + 1;
for(int k = 1,l = 1;k <= 18;++k,l = l << 1)
for(int i = 1;i <= tot - l + 1;++i)
f[i][k] = mymin(f[i][k - 1],f[i + l][k - 1]);
return;
}
int v[MAXN];
int stack[MAXN],top = 0;
bool cmp_dfn(int a,int b){return inp[a] < inp[b];}
ll buildvt()
{
VT::edgenum = 0;
sort(v + 1,v + 1 + v[0],cmp_dfn);
for(int i = 1;i <= v[0];++i)VT::tag[v[i]] = true;
stack[top = 1] = v[1];
for(int i = 2;i <= v[0];++i)
{
int lca = LCA(stack[top],v[i]);
if(lca == stack[top])
{
stack[++top] = v[i];
continue;
}
while(top >= 2)
{
if(inp[lca] < inp[stack[top - 1]])
{
VT::add(stack[top - 1],stack[top]);
--top;
}
else
{
VT::add(lca,stack[top]);
--top;
break;
}
}
if(top == 1 && inp[lca] < inp[stack[top]])
{
VT::add(lca,stack[top]);
stack[top] = lca;
}
if(lca != stack[top])stack[++top] = lca;
stack[++top] = v[i];
}
while(top >= 2)
{
VT::add(stack[top - 1],stack[top]);
--top;
}
for(int i = 1;i <= v[0];++i)VT::w2[v[i]] = dist[v[i]];
int rt = stack[top];
ll res = VT::dp(rt);
for(int i = 1;i <= v[0];++i)VT::tag[v[i]] = false;
return res;
}
}
namespace T1
{
ll ans = 0,pn;
struct edge{int to,nxt;ll v;}ep[MAXN << 1];
int edgenump = 0,linp[MAXN] = {0};
I void addp(int a,int b,ll c)
{
ep[++edgenump] = (edge){b,linp[a],c};linp[a] = edgenump;
ep[++edgenump] = (edge){a,linp[b],c};linp[b] = edgenump;
return;
}
edge e[MAXN << 1];
int edgenum = 1,lin[MAXN] = {0};
I void add(int a,int b,ll c)
{
e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;
e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;
return;
}
bool vir[MAXN];
void rebuild(int k,int fa)
{
R int s = 0;
for(R int i = linp[k];i != 0;i = ep[i].nxt)
{
if(ep[i].to == fa)continue;
if(s == 0)add(k,ep[i].to,ep[i].v),s = k;
else ++pn,vir[pn] = true,add(s,pn,0),add(pn,ep[i].to,ep[i].v),s = pn;
rebuild(ep[i].to,k);
}
return;
}
int siz[MAXN],mx,ed,s;
bool vis[MAXN];
void calcsiz(int k,int fa)
{
siz[k] = 1;
for(int i = lin[k];i != 0;i = e[i].nxt)
{
if(e[i].to == fa || vis[i])continue;
calcsiz(e[i].to,k);
siz[k] += siz[e[i].to];
}
return;
}
void calcedg(int k,int fa)
{
for(int i = lin[k];i != 0;i = e[i].nxt)
{
if(e[i].to == fa || vis[i])continue;
calcedg(e[i].to,k);
int d = max(siz[e[i].to],s - siz[e[i].to]);
if(d < mx)ed = i,mx = d;
}
return;
}
int find_edge(int k)
{
calcsiz(k,0);
ed = -1;s = siz[k];mx = INF;
calcedg(k,0);
return ed;
}
void mark(int k,int c,ll d)
{
VT::col[k] = c;
if(k <= n)
{
T2::v[++T2::v[0]] = k;
VT::w1[k] = d;
}
for(int i = lin[k];i != 0;i = e[i].nxt)
{
if(vis[i] || VT::col[e[i].to] != -1)continue;
mark(e[i].to,c,d + e[i].v);
}
return;
}
void clear(int k)
{
VT::col[k] = -1;
for(int i = lin[k];i != 0;i = e[i].nxt)
{
if(vis[i] || VT::col[e[i].to] == -1)continue;
clear(e[i].to);
}
return;
}
void divide(int k)
{
int edg = find_edge(k);
if(edg == -1)return;
vis[edg] = vis[edg ^ 1] = true;
int u = e[edg].to,v = e[edg ^ 1].to;
T2::v[0] = 0;
mark(u,0,0);mark(v,1,0);
ll res = T2::buildvt() + e[edg].v;
ans = max(ans,res);
clear(u);clear(v);
divide(u);divide(v);
return;
}
}
int main()
{
scanf("%d",&n);
R int a,b;
R ll c;
for(R int i = 1;i < n;++i)
{
a = rd();b = rd();c = rd();
T1::addp(a,b,c);
}
for(R int i = 1;i < n;++i)
{
a = rd();b = rd();c = rd();
T2::add(a,b,c);
}
for(R int i = 1;i < n;++i)
{
a = rd();b = rd();c = rd();
T3::add(a,b,c);
}
memset(VT::col,-1,sizeof(VT::col));
T2::build();
T1::pn = n;
T1::rebuild(1,0);
T3::build();
for(int i = 1;i <= n;++i)VT::dist[i] = T2::dist[i];
T1::divide(1);
cout << T1::ans << endl;
return 0;
}
In tag:
Timeline
About
Toolbox
Friends
Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡