题意：
分析：
这道题是通道的弱化版，所以没什么好说的直接开始推柿子
我们发现存在两个 \(lca\) 边分治没法直接解决有根树过 \(lca\) 的路径，但是 \(dep(x)+dep(y)-dep(lca(x,y))\) 这个东西可以转化成 \(\frac{1}{2}\times (dep(x)+dep(y)+dis(x,y))\) 而 \(dis(x,y)\) 这种树上路径是可以通过树上分治得到的，由于点分治会将树一次划分成多个点，不好处理第二个 \(lca\) 而边分治在多叉转二叉之后，每次分治都只会产生两个点集，便于处理 \(lca\) 所以我们就考虑边分治
每一次找到分治的中心边 \(u\to v\)，断开之后，按照常见的操作，对左右连通块分别染色，记 \(w(x)=dep_1(x)+dis(x,u/v)\) 这样答案转化成了求 \(ans=w(x)+w(y)-dep_2(lca（x,y))+k\) 其中 \(k\) 表示分治边的边权，是个定值，所以我们要最大化 \(w(x)+w(y)-dep_2(lca)\) 我们发现这个东西很类似于树的直径，可以 \(dp\) 求得，所以我们的任务转化成，在 第二棵树上找一个点对，满足两个点的颜色不同，同时尽可能最大化 \(w(x)+w(y)-dep_2(lca)\) 由于每次染色的点集是有限的，所以我们考虑建出虚树，避免无用的枚举，同时建虚树的时候使用 \(O(1)lca\) 降低复杂度，这样复杂度就变成了 \(O(n\log )\)
\(tip:\)
- 虚树上 \(dp\) 时极小值一定要足够小/kk
- 染色时只染原树上有的点，不然对于多叉转二叉建的虚点，在第二棵树上不存在\(lca\)
- 最后一定要特判 \(x==y\) 的情况
代码：
毒瘤题，我连写带调花了两天，重构了好几遍/kk
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
using namespace std;
namespace zzc
{
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
typedef long long ll;
const int maxn = 4e5+5;
const ll inf = 1e18+7;
int n;
int s[maxn][2],num[2],col[maxn],lg[maxn<<1];
ll w[maxn],ans=-inf;
namespace t2
{
struct edge
{
int to,nxt,val;
}e[maxn<<1];
int cnt=1,idx,top,tot;
int head[maxn],dep[maxn],dfn[maxn],st[maxn<<1][20],sta[maxn],q[maxn<<1];
ll dis[maxn],f[maxn][2];
bool vis[maxn];
bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].val=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void dfs(int u,int ff)
{
dfn[u]=++idx;dep[u]=dep[ff]+1;st[idx][0]=u;
for(int i=head[u];i;i=e[i].nxt) if(e[i].to!=ff) dis[e[i].to]=dis[u]+e[i].val,dfs(e[i].to,u),st[++idx][0]=u;
}
int Min(int x,int y)
{
return dep[x]<dep[y]?x:y;
}
int lca(int x,int y)
{
if(dfn[x]>dfn[y]) swap(x,y);
ll k=lg[dfn[y]-dfn[x]+1];
return Min(st[dfn[x]][k],st[dfn[y]-(1<<k)+1][k]);
}
long long calc(int x,int y)
{
return dis[x]+dis[y]-(dis[lca(x,y)]<<1);
}
void init()
{
int a,b,c;
for(ll i=1;i<n;i++)
{
a=read();b=read();c=read();
add(a,b,c);add(b,a,c);
}
dfs(1,0);
for(int j=1;j<=19;j++)
{
for(int i=1;i+(1<<j)-1<=idx;i++)
{
st[i][j]=Min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
memset(head,0,sizeof(head));
}
void DP(int u,ll k)
{
f[u][0]=f[u][1]=-inf;
if(vis[u])f[u][col[u]]=w[u];
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
DP(v,k);
ans=max(ans,k+max(f[u][0]+f[v][1],f[u][1]+f[v][0])-2*dis[u]);
f[u][0]=max(f[u][0],f[v][0]);
f[u][1]=max(f[u][1],f[v][1]);
}
head[u]=0;vis[u]=false;
}
void solve(ll k)
{
cnt=0;tot=0;
for(int i=1;i<=num[0];++i) q[++tot]=s[i][0];
for(int i=1;i<=num[1];++i) q[++tot]=s[i][1];
for(int i=1;i<=tot;++i) vis[q[i]]=true;
sort(&q[1],&q[tot+1],cmp);
top=0;if(q[1]!=1)sta[++top]=1;
for(int i=1;i<=tot;++i)
{
int u=q[i],ff=lca(u,sta[top]);
while(top>1&&dep[sta[top-1]]>=dep[ff]) add(sta[top-1],sta[top],0),--top;
if(ff!=sta[top]) add(ff,sta[top],0),sta[top]=ff;
sta[++top]=u;
}
while(top>1) add(sta[top-1],sta[top],0),--top;
DP(1,k);
}
}
namespace t1
{
struct edge
{
int to,nxt,val;
}e[maxn<<3];
int head[maxn<<2],tmp[maxn<<2],siz[maxn<<2];
ll dis[maxn<<2],dep[maxn<<2];
vector<int> son[maxn<<2];
int N,cnt=0,rt,mx;
bool vis[maxn<<2];
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].val=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void dfs(int u,int ff)
{
for(int i=head[u];i;i=e[i].nxt)
if(e[i].to!=ff) son[u].push_back(e[i].to),dep[e[i].to]=dep[u]+e[i].val,tmp[e[i].to]=e[i].val,dfs(e[i].to,u);
}
void rebuild()
{
memset(head,0,sizeof(head));cnt=1;
for(int i=1;i<=N;++i)
{
int l=son[i].size();
if(l<=2) for(int j=0;j<l;++j) add(i,son[i][j],tmp[son[i][j]]),add(son[i][j],i,tmp[son[i][j]]);
else
{
int ls=++N,rs=++N;
add(i,ls,0);add(ls,i,0);add(i,rs,0);add(rs,i,0);
for(int j=0;j<l;++j)
{
if(j&1)son[ls].push_back(son[i][j]);
else son[rs].push_back(son[i][j]);
}
}
}
}
void getroot(int u,int ff,int Size)
{
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==ff||vis[i>>1])continue;
getroot(v,u,Size);
siz[u]+=siz[v];
int ret=max(siz[v],Size-siz[v]);
if(ret<mx)mx=ret,rt=i;
}
}
void dfs(int u,int ff,int opt)
{
if(u<=n)s[++num[opt]][opt]=u,col[u]=opt;
for(int i=head[u];i;i=e[i].nxt)
if(e[i].to!=ff&&!vis[i>>1])
dis[e[i].to]=dis[u]+e[i].val,dfs(e[i].to,u,opt);
}
void divide(int u,int Size)
{
mx=1e9;getroot(u,0,Size);
if(mx>=1e9)return;
vis[rt>>1]=true;
int old=rt,res=Size-siz[e[rt].to];
num[0]=num[1]=dis[e[rt].to]=dis[e[rt^1].to]=0;
dfs(e[rt].to,0,0);dfs(e[rt^1].to,0,1);
if(!num[0]&&!num[1])return;
for(int i=1;i<=num[0];++i) w[s[i][0]]+=dis[s[i][0]]+dep[s[i][0]];
for(int i=1;i<=num[1];++i) w[s[i][1]]+=dis[s[i][1]]+dep[s[i][1]];
t2::solve(e[rt].val);
for(int i=1;i<=num[0];++i) w[s[i][0]]-=dis[s[i][0]]+dep[s[i][0]];
for(int i=1;i<=num[1];++i) w[s[i][1]]-=dis[s[i][1]]+dep[s[i][1]];
divide(e[old].to,siz[e[old].to]);
divide(e[old^1].to,res);
}
void init()
{
int a,b,c;
for(ll i=1;i<N;i++)
{
a=read();b=read();c=read();
add(a,b,c);add(b,a,c);
}
dfs(1,0);rebuild();
}
}
void work()
{
lg[0]=-1;for(int i=1;i<=800000;i++) lg[i]=lg[i>>1]+1;
n=read();
t1::N=n;
t1::init();
t2::init();
t1::divide(1,t1::N);
ans/=2;
for(int i=1;i<=n;i++) ans=max(ans,t1::dep[i]-t2::dis[i]);
printf("%lld\n",ans);
}
}
int main()
{
zzc::work();
return 0;
}