P4565题解
The_Godfather · · 题解
Problem
题目传送门
题目大意：
- 就是说我们要将树上的点距离按照上式输出。
- LCA 题目的部分都可以倍增，但是复杂度会是
O((n+q) \log n) ，按道理离线的 Tarjan 也不会使用。 - 所以我们会从 DFS+ST 表入手复杂度是
O(n \log n) 符合题意。
Solution
考虑一下要点：
1.由于是 DFS，我们要做到同步更新使
可以一下参考模版：
void dfs(int x)
{
d[x]=d[f[x][0]]+1;//深度从0开始存
for(int i=1;(1<<i)<=d[x];i++)
f[x][i]=f[f[x][i-1]][i-1];
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y=f[x][0]) continue;
f[y][0]=x;
dfs(y);
}
}
int lca(int x,int y)
{
if(d[x]>d[y]) swap(x,y);
while(d[x]<d[y])
{
int k=lg[d[y]-d[x]];
y=f[y][k];
}//y上跳至与x同深度
if(x==y) return x;
int k=lg[d[x]];
for(i=k;~i;i--)
{
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
}
return f[x][0];
}2.但是这道题我们肯定不能只是单个查点，我们还要穿路径长度。所以我们可以这么操作：
void dfs(int u,int ff)
{
dfn[u]=++tim;
dep[u]=dep[ff]+1;
st[0][++sum]=u;
fir[u]=sum;
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)
dis[e[i].v]=dis[u]+e[i].w,dfs(e[i].v,u),st[0][++sum]=u;
low[u]=tim;
}3.将整个读入后为了区分我们总共要有两个 DFS 分别是读入和之后的处理数间距离：
dfs(int u,int ff)
dfs1(int u,int ff,int opt)其次为了防止子树构图越界，我们还要重建一下树。
所以从这里可以看出我们 DFS 只能分开操作，一组找祖先，剩下一组求 Divide 并查找树上的根节点。
然后这道题目就做完了！
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 400400
inline int read() // 快读
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n;
int S[2][MAX],top[2],type[MAX];
int lg[MAX<<1];
ll W[MAX],ans=-1e18;
namespace Tree2 // 求最近公共祖先
{
struct Line{int v,next;ll w;}e[MAX<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v,ll w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}
int dep[MAX];ll dis[MAX];
int dfn[MAX],low[MAX],tim;
int st[20][MAX<<1],sum,fir[MAX];
void dfs(int u,int ff)
{
dfn[u]=++tim;dep[u]=dep[ff]+1;st[0][++sum]=u;fir[u]=sum;
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)
dis[e[i].v]=dis[u]+e[i].w,dfs(e[i].v,u),st[0][++sum]=u;
low[u]=tim;
}
int compare(int a,int b){return dep[a]<dep[b]?a:b;}
void pre()
{
for(int j=1;j<=lg[sum];++j)
for(int i=1;i+(1<<j)-1<=sum;++i)
st[j][i]=compare(st[j-1][i],st[j-1][i+(1<<(j-1))]);
memset(h,0,sizeof(h));
}
int LCA(int u,int v)
{
u=fir[u],v=fir[v];if(u>v)swap(u,v);
int k=lg[v-u+1];
return compare(st[k][u],st[k][v-(1<<k)+1]);
}
bool cmp(int a,int b){return dfn[a]<dfn[b];}
int Q[MAX<<1],T,Stack[MAX];bool vis[MAX];
ll f[MAX][2];
bool book[MAX];
void DP(int u,ll Pls)
{
f[u][0]=f[u][1]=-1e18;if(vis[u])f[u][type[u]]=W[u];
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;DP(v,Pls);
ans=max(ans,Pls+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]);
}
h[u]=0;vis[u]=false;
}
void Solve(ll Pls)
{
cnt=1;T=0;
for(int i=1;i<=top[0];++i)Q[++T]=S[0][i];
for(int i=1;i<=top[1];++i)Q[++T]=S[1][i];
for(int i=1;i<=T;++i)vis[Q[i]]=true;
sort(&Q[1],&Q[T+1],cmp);
int top=0;if(Q[1]!=1)Stack[++top]=1;
for(int i=1;i<=T;++i)
{
int u=Q[i],ff=LCA(u,Stack[top]);
while(top>1&&dep[Stack[top-1]]>=dep[ff])Add(Stack[top-1],Stack[top],0),--top;
if(ff!=Stack[top])Add(ff,Stack[top],0),Stack[top]=ff;
Stack[++top]=u;
}
while(top>1)Add(Stack[top-1],Stack[top],0),--top;
DP(1,Pls);
}
}
namespace Tree1 // 做最后的公式转化
{
struct Line{int v,next,w;}e[MAX<<3];
int h[MAX<<2],cnt=1,V[MAX<<2];
inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}
vector<int> son[MAX<<2];
int N,size[MAX<<2];ll dis[MAX<<2],dep[MAX<<2];
void dfs(int u,int ff)
{
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)
son[u].push_back(e[i].v),dep[e[i].v]=dep[u]+e[i].w,V[e[i].v]=e[i].w,dfs(e[i].v,u);
}
void ReBuild()
{
memset(h,0,sizeof(h));cnt=2;
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],V[son[i][j]]),Add(son[i][j],i,V[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]);
}
}
}
int rt,mx;
bool vis[MAX<<2];
void getroot(int u,int ff,int Size)
{
size[u]=1;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(v==ff||vis[i>>1])continue;
getroot(v,u,Size);size[u]+=size[v];
int ret=max(size[v],Size-size[v]);
if(ret<mx)mx=ret,rt=i;
}
}
void dfs1(int u,int ff,int opt)
{
if(u<=n)S[opt][++top[opt]]=u,type[u]=opt;
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff&&!vis[i>>1])
dis[e[i].v]=dis[u]+e[i].w,dfs1(e[i].v,u,opt);
}
void Divide(int u,int Size)
{
mx=1e9;getroot(u,0,Size);
if(mx>=1e9)return;vis[rt>>1]=true;
int nw=rt,SS=Size-size[e[rt].v];
top[0]=top[1]=dis[e[rt].v]=dis[e[rt^1].v]=0;
dfs1(e[rt].v,0,0);dfs1(e[rt^1].v,0,1);
if(!top[0]&&!top[1])return;
for(int i=1;i<=top[0];++i)W[S[0][i]]+=dis[S[0][i]]+dep[S[0][i]];
for(int i=1;i<=top[1];++i)W[S[1][i]]+=dis[S[1][i]]+dep[S[1][i]];
Tree2::Solve(e[rt].w);
for(int i=1;i<=top[0];++i)W[S[0][i]]-=dis[S[0][i]]+dep[S[0][i]];
for(int i=1;i<=top[1];++i)W[S[1][i]]-=dis[S[1][i]]+dep[S[1][i]];
Divide(e[nw].v,size[e[nw].v]);
Divide(e[nw^1].v,SS);
}
}
int main()
{
n=read();Tree1::N=n;
for(int i=2;i<=n+n;++i)lg[i]=lg[i>>1]+1;
for(int i=1;i<n;++i)
{
int u=read(),v=read(),w=read();
Tree1::Add(u,v,w);Tree1::Add(v,u,w);
}
for(int i=1;i<n;++i)
{
int u=read(),v=read(),w=read();
Tree2::Add(u,v,w);Tree2::Add(v,u,w);
}
Tree1::dfs(1,0);Tree1::ReBuild();
Tree2::dfs(1,0);Tree2::pre();
Tree1::Divide(1,Tree1::N);
ans/=2;
for(int i=1;i<=n;++i)ans=max(ans,Tree1::dep[i]-Tree2::dis[i]);
printf("%lld\n",ans);
return 0;
}