有一个外向树，一个人的两个分身一起，从根节点出发，需要遍历整棵树。每秒可以移动到儿子（可以同时移动），也可以花费0的时间将一个分身瞬移到另一个分身处。问遍历整棵树的最短时间。
(nle 5*10^6)
设关键点为过程中将会瞬移到的点。显然关键点为祖先后代关系。设两个人分别为A和B。
从一个关键点(x)到下一个关键点(y)之间：A首先从(x)出发，将(y)子树外的除了深度最大的之外的叶子结点都遍历（到叶子瞬移回(x)）。然后A从(x)出发，向(y)子树外深度最大的点前进；同时，B从(x)出发，向(y)前进，直到B到达(y)停下。
于是有个DP：设(f_x)表示从根到(x)的最小贡献（其实从子树往上也可以，一样）。
初值(f_{rt}=sum_{iin leaf} dep_i)。转移：(f_yleftarrow f_x-d*sz_y+max(d-mx,0))。其中(d=dis(x,y))，(mx)为(x)子树中(y)子树外距离(x)最远的点。
然后分析性质：
- 如果(d>mx)，那么完全可以先转移到距离(x)为(mx)的点(z)，再转移到(y)。所以只转移(dle mx)即可。
- 设(mx)所在的(x)的儿子(u)的子树内。如果(yin subtree(u))，则完全可以先从(x)转移到(u)，再转移到(y)。所以转移的时候，如果保证(y otin subtree(u))，也可以得到正确结果。
有了这两个性质其实就可以做了：长链剖分，对于一个点来说，它往下的长链需要更新的长度是次长链长度，其它链需要更新的长度是它们自身的长度。时间是(O(n))。
其实还可以进一步分析性质：一个点只需要被能贡献到它的深度最大的祖先更新。因为如果有这样的两个祖先(x_0,x_1)，(dep_{x0}<dep_{x1})，那么(x_0)可以先更新到(x_1)（必定有(dle mx)）然后再更新到(y)。
然后就可以倒着做，每个子树用个链表存有哪些儿子还没有被贡献过，接上父亲边之后将被能被贡献的点贡献并删去即可。
我没想到C++空间是那么阴间，明明题目说是512MB，我静态空间才刚刚过256MB，怎么会挂？
因为noi linux上不会测空间所以我在gmoj和uoj上测了下。看如下代码：
void dp(int x){
if (last[x]){
if (last[x]->las){
int sec=0;
for (EDGE *ei=last[x];ei;ei=ei->las)
if (ei->to!=hs[x]){
for (int y=ei->to,d=1;y;y=hs[y],++d)
f[y]=min(f[y],-(ll)d*sz[y]+f[x]);
sec=max(sec,len[ei->to]+1);
}
for (int y=hs[x],d=1;d<=sec;y=hs[y],++d)
f[y]=min(f[y],-(ll)d*sz[y]+f[x]);
}
else{
int y=last[x]->to;
f[y]=min(f[y],-sz[y]+1+f[x]);
}
for (EDGE *ei=last[x];ei;ei=ei->las)
dp(ei->to);
}
else
ans=min(ans,f[x]);
}
按理来说我递归时只有参数和枚举边的循环变量保留在栈中，其它变量的应该都是在递归前释放了或者在递归之后才定义啊？
但事实上，以上程序中：变量sec,y,d,ei,甚至还有min,max的返回值，在释放了之后没有回收空间？
改成下面这样，空间优化显著：
void dp(int x){
if (last[x]){
for (EDGE *ei=last[x];ei;ei=ei->las)
dp(ei->to);
static int sec,y,d;
static EDGE *ei;
if (last[x]->las){
sec=0;
for (ei=last[x];ei;ei=ei->las)
if (ei->to!=hs[x]){
for (y=ei->to,d=1;y;y=hs[y],++d)
if (f[x]>-(ll)d*sz[y]+f[y])
f[x]=-(ll)d*sz[y]+f[y];
if (sec<len[ei->to]+1)
sec=len[ei->to]+1;
}
for (y=hs[x],d=1;d<=sec;y=hs[y],++d)
if (f[x]>-(ll)d*sz[y]+f[y])
f[x]=-(ll)d*sz[y]+f[y];
}
else{
y=last[x]->to;
if (f[x]>-sz[y]+1+f[y])
f[x]=-sz[y]+1+f[y];
}
}
else
f[x]=0;
}
然而这不是最终版本，因为开了O2之后，不知道为什么又多了好多空间。非得逼我把邻接表中的指针换成int才卡过。
using namespace std;
#include <bits/stdc++.h>
#define N 5000005
#define INF 1000000000
#define ll long long
int n;
struct EDGE{
int to,las;
} e[N];
int ne;
int last[N];
void link(int u,int v){
e[++ne]={v,last[u]};
last[u]=ne;
}
int st[N],tp;
void read(){
scanf("%d",&n);
char ch=getchar();
while (ch!='(' && ch!=')')
ch=getchar();
//n=5000000;
//char ch='(';
int cnt=0;
st[tp=1]=++cnt;
for (int i=1;i<n+n;++i){
ch=getchar();
//ch=(i<n?'(':')');
if (ch=='('){
++cnt;
link(st[tp],cnt);
st[++tp]=cnt;
}
else
--tp;
}
}
int sz[N],len[N],hs[N];
ll all;
void predfs(int x,int d){
len[x]=0;
if (last[x]){
for (int ei=last[x];ei;ei=e[ei].las){
predfs(e[ei].to,d+1);
sz[x]+=sz[e[ei].to];
if (len[e[ei].to]+1>len[x])
len[x]=len[e[ei].to]+1,hs[x]=e[ei].to;
}
}
else{
sz[x]=1;
all+=d;
}
}
ll f[N],ans;
void dp(int x){
if (last[x]){
for (int ei=last[x];ei;ei=e[ei].las)
dp(e[ei].to);
static int sec,y,d,ei;
if (e[last[x]].las){
sec=0;
for (ei=last[x];ei;ei=e[ei].las)
if (e[ei].to!=hs[x]){
for (y=e[ei].to,d=1;y;y=hs[y],++d)
if (f[x]>-(ll)d*sz[y]+f[y])
f[x]=-(ll)d*sz[y]+f[y];
if (sec<len[e[ei].to]+1)
sec=len[e[ei].to]+1;
}
for (y=hs[x],d=1;d<=sec;y=hs[y],++d)
if (f[x]>-(ll)d*sz[y]+f[y])
f[x]=-(ll)d*sz[y]+f[y];
}
else{
y=e[last[x]].to;
if (f[x]>-sz[y]+1+f[y])
f[x]=-sz[y]+1+f[y];
}
}
else
f[x]=0;
}
int main(){
read();
predfs(1,0);
memset(f,127,sizeof f);
dp(1);
ans=f[1]+all;
printf("%lld
",ans);
return 0;
}