（四边形不等式的套路题）
对于某一组$a_{i}$，显然可以区间dp，设$f_{l,r}$表示区间$[l,r]$的答案，则转移即
$$
f_{l,r}=\begin{cases}0&(l=r)\\\sum_{i=l}^{r}\sum_{j=l}^{r}dist(a_{i},a_{j})+\min_{l\le i<r}(f_{l,i}+f_{i+1,r})&(l<r)\end{cases}
$$
为了方便，对于$l<r$定义$f_{l,r}$的最优决策为后者取到$\min$时的（任意一个）$i$
记$S_{l,r}=\sum_{i=l}^{r}\sum_{j=l}^{r}dist(a_{i},a_{j})$，不难发现其满足单调性四和边形不等式，即
$$
\forall a_{1}\le a_{2}\le b_{1}\le b_{2},\begin{cases}S_{a_{2},b_{1}}\le S_{a_{1},b_{2}}\\S_{a_{1},b_{1}}+S_{a_{2},b_{2}}\le S_{a_{1},b_{2}}+S_{a_{2},b_{1}}\end{cases}
$$
由此，我们就可以得到$f$满足四边形不等式，证明如下——
引理1：$f$满足四边形不等式当且仅当$\forall a<b,f_{a,b}+f_{a+1,b+1}\le f_{a,b+1}+f_{a+1,b}$
若$a+1<b$，即有$f_{a+1,b}+f_{a+2,b+1}\le f_{a+1,b+1}+f_{a+2,b}$
将两式相加，消项后即有$f_{a,b}+f_{a+2,b+1}\le f_{a,b+1}+f_{a+2,b}$
不难发现记将$a+1$变为了$a+2$，以此类推即有$f_{a_{1},b}+f_{a_{2},b+1}\le f_{a_{1},b+1}+f_{a_{2},b}$
类似地，也可以将$b+1$变为$b+2$，以此类推即得到四边形不等式
另外，对于$a_{1}=a_{2}$或$b_{1}=b_{2}$的情况，四边形不等式显然成立
此时即只有两维，对$b-a$归纳，在$b-a\le 2$时简单分析显然成立
若$b-a<k$时成立，考虑$b-a=k$时：
设$f_{a,b+1}$的最优决策为$x$，$f_{a+1,b}$的最优决策为$y$，不妨假设$x\le y$（对于$x>y$是类似地），即有
$$
f_{a,b+1}+f_{a+1,b}=(f_{a,x}+f_{x+1,b+1}+S_{a,b+1})+(f_{a+1,y}+f_{y+1,b}+S_{a+1,b})
$$
而对于$f_{a,b}$和$f_{a+1,b+1}$，显然该处决策也对其取$\min$，即有
$$
f_{a,b}+f_{a+1,b+1}\le (f_{a,x}+f_{x+1,b}+S_{a,b})+(f_{a+1,y}+f_{y+1,b+1}+S_{a+1,b+1})
$$
将两者比较，消掉相同项以及$S$的四项（对应其四边形不等式），即求证
$$
f_{x+1,b+1}+f_{y+1,b}\le f_{x+1,b}+f_{y+1,b+1}
$$
不难发现这也即为四边形不等式，由归纳显然成立
综上，即证明了$f$满足四边形不等式
引理2：若$f$满足四边形不等式，则$f$具有决策单调性
首先，来解释一下此处的"决策单调性"：令$g_{l,r}$为$[l,r]$处的最优决策，则$g_{l,r-1}\le g_{l,r}\le g_{l+1,r}$
不妨考虑$g_{l,r-1}\le g_{l,r}$（对于$g_{l,r}\le g_{l+1,r}$是类似地），令$j=g_{l,r-1}$，也即求证$\forall l\le i<j$（对于$f_{l,r}$）在i处转移不如在$j$处转移，显然由此即可得到$j\le g_{l,r}$
具体的，已知$f_{l,j}+f_{j+1,r-1}\le f_{l,i}+f_{i+1,r-1}$，构造$f_{i+1,r-1}+f_{j+1,r}\le f_{i+1,r}+f_{j+1,r-1}$（根据f的四边形不等式），将两者相加即$f_{l,j}+f_{j+1,r}\le f_{l,i}+f_{i+1,r}$，也即所求证
由此，枚举的范围变为$[g_{l,r-1},g_{l+1,r}]$，将长度求和即$\sum_{l=1}^{n}\sum_{r=l+1}^{n}(g_{l+1,r}-g_{l,r-1})\le \sum_{l=1}^{n}g_{l,n}$，后者显然为$o(n^{2})$，也即可$o(n^{2})$求出初始$a_{i}$的dp数组
下面，考虑如何修改：假设加入元素后序列长度为$n$，相比原来要额外求出的即$\forall 1\le i\le n,f_{i,n}$，显然其仍满足$g_{i,n-1}\le g_{i,n}\le g_{i+1,n}$，但此时长度求和后并不能相消，由于均摊会使得其退化到$o(rn^{2})$
下面，考虑更严格的单调性——若对于$l\le x<y<r$对$f_{l,r}$在$x$处不如$y$处，则对$f_{l-1,r}$在$x$处也不如$y$处
（事实上，满足决策单调性的通常都满足此性质）
由此，从后往前处理出$g_{i,n}$（被划分为若干个区间），并通过二分来求出当前加入位置的影响即可
综上，总复杂度为$o(m^{2}+n^{2}+rn\log n)$，可以通过
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 2005
4 #define M 305
5 #define ll long long
6 struct Edge{
7 int nex,to,len;
8 }edge[N<<1];
9 deque<int>Q;
10 int t,n,q,E,x,y,head[N],l[M],a[M][N],pos[M][N],L[N],R[N],g[N][N];
11 ll d[N][N],S1[N][N],S2[M][N],f[N][N],F[M][N];
12 void add(int x,int y,int z){
13 edge[E]=Edge{head[x],y,z};
14 head[x]=E++;
15 }
16 void dfs(int k,int fa,ll s,int st){
17 d[st][k]=s;
18 for(int i=head[k];i!=-1;i=edge[i].nex)
19 if (edge[i].to!=fa)dfs(edge[i].to,k,s+edge[i].len,st);
20 }
21 ll get_S(int i,int x,int y){
22 if (x>y)return 0;
23 if (y<=l[0])return S1[x][y];
24 return S2[pos[i][y]][x];
25 }
26 ll get_f(int i,int x,int y){
27 if (y<=l[0])return f[x][y];
28 return F[pos[i][y]][x];
29 }
30 ll calc(int i,int j,int k){
31 if (j>=k)return 1e18;
32 return get_f(i,j,k-1)+F[i][k]+S2[i][j];
33 }
34 int main(){
35 scanf("%d",&t);
36 while (t--){
37 scanf("%d%d%d",&n,&l[0],&q);
38 E=0;
39 memset(head,-1,sizeof(head));
40 for(int i=1;i<=n;i++){
41 scanf("%d%d",&x,&y);
42 add(x,i,y),add(i,x,y);
43 }
44 for(int i=0;i<=n;i++)dfs(i,-1,0,i);
45 for(int i=1;i<=l[0];i++)scanf("%d",&a[0][i]);
46 for(int i=1;i<=l[0];i++)S1[i][i]=f[i][i]=0;
47 for(int i=l[0];i;i--){
48 ll s=0;
49 for(int j=i+1;j<=l[0];j++){
50 s+=d[a[0][i]][a[0][j]];
51 S1[i][j]=S1[i+1][j]+s;
52 if (i+1==j){
53 g[i][j]=i;
54 f[i][j]=S1[i][j];
55 }
56 else{
57 f[i][j]=1e18;
58 for(int k=g[i][j-1];k<=g[i+1][j];k++)
59 if (f[i][k]+f[k+1][j]+S1[i][j]<f[i][j]){
60 g[i][j]=k;
61 f[i][j]=f[i][k]+f[k+1][j]+S1[i][j];
62 }
63 }
64 }
65 }
66 printf("%lld\n",(f[1][l[0]]<<1));
67 for(int i=1;i<=q;i++){
68 scanf("%d%d",&x,&y);
69 l[i]=l[x];
70 for(int j=1;j<=l[i];j++){
71 a[i][j]=a[x][j];
72 pos[i][j]=pos[x][j];
73 }
74 a[i][++l[i]]=y,pos[i][l[i]]=i;
75 ll s=S2[i][l[i]]=F[i][l[i]]=0;
76 L[l[i]]=1,R[l[i]]=l[i];
77 Q.clear(),Q.push_back(l[i]);
78 for(int j=l[i]-1;j;j--){
79 s+=d[a[i][j]][y];
80 S2[i][j]=get_S(i,j,l[i]-1)+s;
81 while ((!Q.empty())&&(j<L[Q.front()]))Q.pop_front();
82 F[i][j]=calc(i,j,Q.front());
83 while ((!Q.empty())&&(calc(i,R[Q.back()],j)<calc(i,R[Q.back()],Q.back())))Q.pop_back();
84 if (Q.empty())L[j]=1,R[j]=j;
85 else{
86 int p=Q.back(),l=L[p],r=R[p];
87 while (l<r){
88 int mid=(l+r>>1);
89 if (calc(i,mid,p)<calc(i,mid,j))r=mid;
90 else l=mid+1;
91 }
92 L[Q.back()]=l;
93 if (l==1)continue;
94 L[j]=1,R[j]=l-1;
95 }
96 Q.push_back(j);
97 }
98 printf("%lld\n",(F[i][1]<<1));
99 }
100 }
101 return 0;
102 }