Wind of Change/模拟赛T4 题解
题意
给定两颗结点数为 $n$ 的树 $T1$ 和 $T2$，定义 $dis(T,x,y)$ 表示在树 $T$ 上 $x$ 到 $y$ 的路径上所有边的权值和。
现在求 $\forall x \in [1,n] , \min\limits_{1\le y\le n,x\neq y}dis(T1,x,y)+dis(T2,x,y)$。
一道相当好的题。
此题 $O(n\log^2{n})$ 做法可过，但是 black_trees讲了一种 $O(nlogn)$ 并且可以扩展到三棵树的写法，但是稍微有点点复杂。
这篇文章将会分思路和实现两个方面讲解。
思路
首先将 $T1$ 进行点分治，然后对于每一次分治出来的子树 $T$ ，记 $T$ 的根为 $root$。
如图，当前的 $root$ 即为 $4$。
然后在 $T$ 中遍历一遍，记录 $T$ 中每个结点 $u$ 到 $root$ 的距离，记为 $a_u$，如果没有则为 $\infty$，然后将 $a_u$ 影射到 $T2$ 上，即在 $T2$ 上点 $u$ 多了一个点值 $a_u$。然后在 $T2$ 上面跑树形DP即可。
下面是（不太严谨的）正确性证明：
在这里，如果对于 $x$，使得 $dis(T1,x,y)+dis(T2,x,y)$ 最小的结点为 $y$，我们就称 $x$ 的最佳匹配为 $y$。
如果结点 $x$ 的最佳匹配为 $y$，那么它们的 lca 必定会作为 $T$ 的 $root$（正确性显然），那么此时 $dis(T1,x,y)+dis(T2,x,y)$ 一定会被统计到，故成立。
现在处理在 $T2$ 上面的树形DP部分。
首先我们意识到：如果我们真的直接在 $T2$ 上面跑树形DP，那么直接是 $O(n^2logn)$ 的时间复杂度，弗如暴力。发现其实很多点都是不会产生贡献的，那么我们就需要一个方法将我们不需要的结点删去，是的，就是（一个NOI大纲10级算法）虚树。
所以我们只需要将 $T$ 中的结点，在 $T2$ 的基础上建虚树，再跑DP即可。
好，现在只差一个部分了。
令 $f_{u,0/1}$ 表示 $y$ 在以 $u$ 为根的子树中 $dis(T1,x,y)+dis(T2,x,y)$ 的最小值和次小值。
令 $g_{u,0/1}$ 表示 $y$ 在整棵树中 $dis(T1,x,y)+dis(T2,x,y)$ 的最小值和次小值。
$$ f_{u,0}=\min\limits_{v \in son(u)}{\min f_v,a_v}+c_{u,v} $$
$$
g_{u,0}=
\begin{cases}
\min{g_{fa,1},a_fa}+c_{u,fa}, & g_{fa,0}=min{f_{u,0},a_u}+c(u,fa), \\
\min{g_{fa,1},a_fa}+c_{u,fa}, & g_{fa,0}\neq min{f_{u,0},a_u}+c(u,fa)
\end{cases}
$$
第一个都好理解，但是第二个为什么要特判的原因是如果 $u$ 的父亲是由 $u$ 转移过来的话，那么可能导致答案没有正确地被统计，如例（不考虑 $a$ 的影响）：
在上图中，如果没有特判，则 $g_{u,0}$ 为 $2$ 而不是 $11$，这会导致我们计算的答案变小（话说这都是树形DP基本操作了）。
之后答案就是 $\min{s[x]+g[x][0]}$。
实现
这道题，要写三颗树，如果你像我一样将每棵树封装一下话，起码要写三次邻接链表（或者三个 vector），但是我们可以用 c++ 的一些神奇语法：继承。
所以我只写了个 Graph 的结构体然后三颗树都继承一下就行了
struct Graph
{
struct sss
{
int q,w,e,nxt;
}a[N];
int cnt,head[N];
void adde(int q,int w,int e)
{
a[++cnt].q=q;
a[cnt].w=w;
a[cnt].e=e;
a[cnt].nxt=head[q];
head[q]=cnt;
}
};
struct Virtual_Tree:public Graph
{
...
}T3;
struct Tree_2:public Graph
{
...
}T2;
struct Tree_1:public Graph
{
...
}T1;
点分治
先上代码：
struct Tree_1:public Graph
{
vector<pii>t;
int root,s[N],f[N],sum,vis[N],g[N];
void getroot(int x,int fa)
{
s[x]=1;f[x]=0;
for(int i=head[x];i;i=a[i].nxt)
{
if(a[i].w!=fa&&!vis[a[i].w])
{
getroot(a[i].w,x);
s[x]+=s[a[i].w];
f[x]=max(f[x],s[a[i].w]);
}
}
f[x]=max(f[x],sum-s[x]);
if(f[x]<f[root])root=x;
}//点分治板子
void dfs(int x,int fa)
{
t.push_back(mp(x,g[x]));//将T中结点压入vector，一会儿传给T2
for(int i=head[x];i;i=a[i].nxt)
{
if(a[i].w!=fa&&!vis[a[i].w])
{
g[a[i].w]=g[x]+a[i].e;
dfs(a[i].w,x);
}
}
}//g是上文提到的a
void work(int x)
{
for(pii x:t)g[x.first]=0;
t.clear();
dfs(x,0);
int root=T2.build(t);
T3.dfs1(root,0);
T3.dfs2(root,0);
}//把 T 中的子树交给 T2 和虚树处理
void dfz(int x)
{
vis[x]=1;
work(x);
for(int i=head[x];i;i=a[i].nxt)
{
if(vis[a[i].w])continue;
sum=s[a[i].w];f[0]=N,root=0;
getroot(a[i].w,0);
getroot(root,0);
dfz(root);
}
}//板子
}T1;
建虚树
虚树详情在这里
建虚树时，要用 lca 等东西，所以要先预处理，然后虚树内既要存边权也要存点权所以比较麻烦。
struct Tree_2:public Graph
{
int p[N][25],d[N],top,dfn[N],num,s[N];
pii st[N];
int LCA(int x,int y)
{
if(d[x]<d[y])swap(x,y);
for(int i=20;i>=0;i--)if(d[p[x][i]]>=d[y])x=p[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)if(p[x][i]!=p[y][i])x=p[x][i],y=p[y][i];
return p[x][0];
}
void dfs(int x,int fa)
{
p[x][0]=fa;
d[x]=d[fa]+1;
dfn[x]=++num;
for(int i=1;i<=20;i++)p[x][i]=p[p[x][i-1]][i-1];
for(int i=head[x];i;i=a[i].nxt)
{
if(a[i].w!=fa)
{
s[a[i].w]=s[x]+a[i].e;
dfs(a[i].w,x);
}
}
}
int build(vector<pii>t)
{
sort(t.begin(),t.end(),cmp);
st[top=1]=t[0];T3.head[t[0].first]=0;T3.cnt=0;
int root=t[0].first,mn=dfn[root];//虚树的根结点
for(pii __:t)//建虚树部分，感性理解
{
int x=__.first,_=__.second;
if(__!=t[0])
{
int lca=LCA(x,st[top].first);
if(lca!=st[top].first)
{
while(dfn[lca]<dfn[st[top-1].first])
{
T3.adde(st[top-1].first,st[top].first,s[st[top].first]-s[st[top-1].first]);
T3.adde(st[top].first,st[top-1].first,s[st[top].first]-s[st[top-1].first]);
T3.s[st[top].first]=st[top].second;
top--;
}
if(dfn[lca]>dfn[st[top-1].first])
{
T3.head[lca]=0;
T3.adde(lca,st[top].first,s[st[top].first]-s[lca]);
T3.adde(st[top].first,lca,s[st[top].first]-s[lca]);
T3.s[st[top].first]=st[top].second;
st[top]=mp(lca,inf);
if(dfn[lca]<mn)mn=dfn[lca],root=lca;
}
else
{
T3.adde(lca,st[top].first,s[st[top].first]-s[lca]);
T3.adde(st[top].first,lca,s[st[top].first]-s[lca]);
T3.s[st[top].first]=st[top].second;
top--;
}
}
T3.head[x]=0,st[++top]=mp(x,_);if(dfn[x]<mn)mn=dfn[x],root=x;
}
}
for(int i=1;i<top;i++)
{
T3.adde(st[i].first,st[i+1].first,s[st[i+1].first]-s[st[i].first]);
T3.adde(st[i+1].first,st[i].first,s[st[i+1].first]-s[st[i].first]);
T3.s[st[i].first]=st[i].second;
}
T3.s[st[top].first]=st[top].second;
return root;//返回根
}
}T2;
换根DP
最简单的一部分
struct Virtual_Tree:public Graph
{
int s[N],f[N][2],g[N][2];
void dfs1(int x,int fa)
{
f[x][0]=f[x][1]=inf;
for(int i=head[x];i;i=a[i].nxt)
{
if(a[i].w^fa)
{
dfs1(a[i].w,x);
int p=min(s[a[i].w],f[a[i].w][0])+a[i].e;
if(p<f[x][0])f[x][1]=f[x][0],f[x][0]=p;
else f[x][1]=min(p,f[x][1]);
}
}
}
void dfs2(int x,int fa)
{
g[x][0]=f[x][0];
g[x][1]=f[x][1];
for(int i=head[x];i;i=a[i].nxt)
{
if(a[i].w==fa&&fa)
{
int p=min(s[x],g[x][0])+a[i].e,q;
if(p==g[fa][0])q=min(g[fa][1],s[fa])+a[i].e;
else q=min(g[fa][0],s[fa])+a[i].e;
if(q<g[x][0])g[x][1]=g[x][0],g[x][0]=q;
else g[x][1]=min(g[x][1],q);
}
}
for(int i=head[x];i;i=a[i].nxt)if(a[i].w!=fa)dfs2(a[i].w,x);;
ans[x]=min(ans[x],g[x][0]+s[x]);//更新答案
}
}T3;
这道题就这样做完了。