[集训队作业2018]蜀道难——TopTree+贪心+树链剖分+链分治+树形DP

题目链接：

[集训队作业2018]蜀道难

题目大意：给出一棵$n$个节点的树，要求给每个点赋一个$1\sim n$之内的权值使所有点的权值是$1\sim n$的一个排列，定义一条边的权值为两端点权值差的绝对值，要求对于任意两点间的路径要么路径上所有点的点权单调，要么存在路径上的第三个点到这两个点的路径分别单调(即两点间路径先单调递增再单调递减或先单调递减再单调递增)。求出整棵树最小边权和，并支持动态插入点之后完成上述问题。

前言：

这道题综合性比较强且代码量及细节非常多，是迄今为止我做过最神仙的题(没有之一)。题目大致可分成贪心、树形DP、树链剖分、TopTree、及链分治五部分，我们分步讲解。

贪心：

1、题目中对任意两点路径的要求可以转化为“存在一个点到所有点的路径都单调”。

这个可以用反证法证明：

如果上述结论不符，那么存在一个点$x$到一个叶子节点$z$的路径上有题目中所述的第三个节点$y$，假设$x$到$y$单调递减，$y$到$z$单调递增。我们以$x$为根，那么除$y,z$所在子树之外的其他$x$的子树中的点到$x$必须要单调递减，否则这个点$->x->y->z$的路径被分成了单调的三段。我们再讨论$x->y$路径上的点及他们的子树，这些点到$y$必须也要单调递减，否则这些点到$z$的路径也被分成了三段。然后讨论$y$到$z$路径上的点及他们子树中的点(不包括$y$其他子树中的点)，这些点到$y$的路径要单调递减，否则他们到$x$的路径被分成了三段。至于$y$其他子树中的点到$y$可以单调递增也可以单调递减。这样所有点到$y$的路径就都是单调的了，所以上述结论成立。

这样，我们以点$y$为根，那么有一部分子树是单调递增的(即一个节点的点权小于每个子节点的点权，下同理)，另一部分是单调递减的，这也就可以将整棵树看作是共用堆顶的一个大根堆和一个小根堆(并不是二叉堆)。我们先来考虑一个堆的情况，以小根堆为例。

考虑堆中的一个子树，它的值域为$[l,r]$(即子树中最小点权与最大点权)，那么将它的值域范围减小一定会使这棵子树内部的答案减小，假设将值域范围减小了$d$，那么子树内部的答案至少会减小$d$。现在考虑互不包含的两棵子树$T1,T2$，假设$T1$的值域为$[l1,r1]$，$T2$的值域为$[l2,r2]$，且$l1<l2<r1<r2$，那么显然权值在$[l2,r1]$值域范围内的点一定有$T1$中点的点权大于$T2$中点的点权。现在我们将点权在$[l2,r1]$范围内的点重新分配，使得分配后的$r1<l2$，显然两棵子树的内部答案都会减小。这就启示我们每棵子树中的点权值域要连续。

2、对于一个堆，必然存在一种最优策略使得每棵子树中点的点权值域连续

这个也很好证明，假设有一棵子树的点权值域不连续，那么一定有另一棵子树与这棵子树的值域有交集，将交集消除显然会使两棵子树的答案更优，因此每棵子树内的点权值域必然连续。

那么一棵子树的答案就可以看作是每个点与它所有子节点之间的边权和之和。假设一个父节点$u$的点权为$x$，那么每棵子树的值域就是$[x+1,x+size1],[x+size1+1,x+size1+size2]……$(其中$size[i]$表示第$i$棵子树的大小)，显然$u$的每个子节点点权是以他们为根的子树中最小的点权，即$x+1,x+size1+1,x+size1+size2+1……$，$u$与这些子节点之间的边权和就是$1+(size1+1)+(size1+size2+1)……$。可以发现每个子节点的子树大小会影响后面所有子节点与$u$之间边的边权，所以应该贪心地将$size$小的子树排在前面。我们将所有子树按子树大小从大到小排序，假设一棵子树的排名为$p_{i}$，那么$u$与这些子节点之间的边的边权和就是$\sum\limits_{i}^{ }size_{i}(p_{i}-1)+1$。

那么现在再来考虑共用堆顶的这两个堆，即根节点与其子节点之间边的贡献，如果只有大根堆或者小根堆那么边权和还是上面那个式子。这也就是说每个点的子树大小还要影响后面所有子节点到根的边的贡献。而如果我们将这些子树按大小顺序交错分给大根堆和小根堆，那么决策显然是最优的，每个子节点的子树大小只会影响后面一半子节点的贡献，即代价为$\sum\limits_{i}^{ }size_{i}\left \lfloor \frac{p_{i}-1}{2}\right \rfloor+1$。

树形DP：

有了上面的贪心结论，就可以解决静态树的答案了。我们将每个点的出边指向的子节点按子树大小从大到小排序。对于每条有向边(将无向边看作两条有向边)维护有向边指向点$x$的子树中所有边的贡献，这一步通过两次树形DP即可实现，具体实现参见代码。然后枚举每个点为树的根，将子节点按子树大小交错分给大根堆和小根堆统计出以每个点为根的答案取最小值即可。

树链剖分：

可以发现当确定了根节点之后，每个点与它父节点之间边的代价只与这个点在它父节点的子节点中的排名有关。对于统计最终答案，我们无法确定最终答案是以哪个点为根，那么我们不妨换个思路：暴力维护以每个点为根时答案的最优值。我们先考虑维护以$x$为根的答案时，添加一个点对以$x$为根的答案的影响。显然，子节点排名顺序可能会改变的点(我们称之为改变点)一定是添加点到$x$路径上的点，更进一步地来说，将整棵树重链剖分，如果一个在添加点到$x$路径上的点$y$是它的父节点$z$的轻儿子，那么$z$的子节点的顺序就可能会改变，而一个路径上的轻儿子最多只有$logn$个，所以对于以$x$为根的答案来说改变点只有$logn$个。而我们要求以所有点为根的答案，那么这样改变点的总数就有可能是$O(n)$级别的，这显然并不优秀，所以我们需要找到一个点$p$使得以这个点为根(并非是最优答案的那个根，而是树结构上的一个根)做重链剖分，使得改变点的总数在一个可接受的级别内。实际上确实存在这么一个$p$点且可以使改变点的总量在$O(logn)$级别，而这个点就是树的重心。我们假设添加点为$u$，要维护以$v$为根的答案，$u,v$两点的$lca$是$x$，那么改变点就是$(u,v)$路径上的一些点，对于$(u,x)$路径，改变点自然是路径上的轻儿子的父节点；而对于$(x,v)$路径上的点，因为在以$v$为根时，这些点的子树中都包含点$p$(即重心)，那么这些点一定是重儿子，所以$(x,v)$路径上不会存在改变点。这样改变点的总数就是$(u,p)$路径上轻儿子点的数量。

剩下的部分就是添加一个点后对整棵树对应的修改了，修改可分为两部分：一部分是对树的结构进行修改，另一部分是对每个点维护的信息进行修改。

TopTree：

对树结构的修改分为调换子节点顺序和移动重心两部分。说到动态加点并动态换根维护重心，自然可以想到用LCT来维护，而还需要调换子节点顺序，那么支持这些操作的就只有TopTree了(TopTree详见TopTree讲解)。初始构建TopTree只需要将树形DP维护的信息加到每个点，然后按子树从大到小加入每个点的子节点即可，维护轻儿子的splay的key值也是按子树大小来维护(值得注意的是子树越大的节点在splay中越靠前)。

对于调换子节点顺序，我们每次在TopTree上跳重链，对于轻儿子$x$在它父节点维护轻儿子的splay上二分查找找到$x$这个子树添加一个点后在父节点轻儿子中的位置然后调换过去，注意这个点可以替代父节点原来的重儿子；对于移动重心，因为添加一个节点重心最多只会移动一个节点且一定是原重心的重儿子，所以只要判断是否需要移动重心，如果移动就将原重心变成它重儿子的重儿子，并将原重心的最重轻儿子变成它的重儿子。

链分治：

这部分是整道题细节最多的部分。对于每个点我们需要维护以这个点为根的答案$sum$(即根的子节点到根的边贡献为$size_{i}\left \lfloor \frac{p_{i}-1}{2}\right \rfloor+1$)及以这个点为根时整棵树只分成一个堆时的答案$val$(即根的子节点到根的边贡献为$size_{i}(p_{i}-1)+1$)。我们假设一次添加节点是将$x$连到$fa$的下面，我们将整棵树所有的点分成几部分讨论(我们称$x$到根的路径为修改链)：

1、对于每个点$u$，假设他与$x$的$lca$为$v$，那么$u$的$val,sum$的值都要加上$v$下面的修改链上轻儿子与父节点之间的新增贡献(即这个轻儿子的排名，因为子树大小加了$1$)。这也就是说修改链上每个轻儿子与父节点之间边的的新增贡献要加到除轻儿子子树之外的所有点的答案上，这样不好修改，所以我们可以记录每个修改链上的轻儿子这样的新增贡献$val$的总和，每次将轻儿子子树内所有节点的答案减去$val$，再给整棵树每个节点都加上$val$就好了。

2、对于修改链的重链上的每个点$x$(重链下端点除外)，当以$x$为根时，添加点位于$x$第二大的子树中，所以需将$x$的$val$值加$1$(注意$sum$的值不需增加)；但对于修改链的重链上的点的轻儿子，$val,sum$的值都需要加$1$。(这里注意根节点的轻儿子需要特判)

3、对于修改链上的重链的下端点$x$(包括$fa$)，当以$x$为根时，这个修改链上的轻儿子与$x$直接相连，因此$sum$的增量是$\left \lfloor \frac{p_{i}-1}{2}\right \rfloor$。

剩下一些细节的修改在这里就不一一说明，具体可以看代码，总之链分治时注意轻重链交接处、根节点及重链上的点与其轻儿子之间的细节。

代码中附注释。

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define INF 1e18;
using namespace std;
ll ans;
int x,y;
int n,m;
int cnt;
int flag;
int tot=1;
int r[600010];//翻转标记
int f[600010];//父节点
ll val[600010];//将整棵树只分成一个堆时的答案
ll sum[600010];//以每个点为根的答案
int fa[400010];//树形DP时的父节点
int to[400010];
int sz[400010];//每条边指向点的子树大小
ll cost[400010];//每条边指向点的子树答案
int head[200010];
int next[400010];
int size[600010];//splay子树大小
int root[200010];
int s[600010][3];//子节点，0为左儿子、1为右儿子、2为轻儿子
ll son_min[600010];//子树答案最小值
ll son_val[600010];//子树下传标记
ll sum_cost[200010];//子树答案
vector<int>q[200010];
int sum_size[600010];//TopTree子树大小
ll chain_min[600010];//重链最小值
ll chain_val[600010];//重链下传标记
ll point_val[600010];//val数组下传标记
inline bool get(int rt)
{
	return rt==s[f[rt]][1];
}
inline void initial(int rt)//初始化
{
	sum_size[rt]=1;
}
inline int build()//新建节点
{
	int rt=++cnt;
	if(!flag)
	{
		flag=1;
		val[0]=sum[0]=INF;
		chain_min[0]=son_min[0]=INF;
	}
	initial(rt);
	return rt;
}
inline void link(int rt,int num,int x)//连边
{
	s[rt][num]=x;
	f[x]=rt;
}
inline void flip(int rt)//子树翻转
{
	r[rt]^=1;
	swap(s[rt][0],s[rt][1]);
}
inline void chain_add(int rt,ll x)
{
	val[rt]+=x;
	sum[rt]+=x;
	chain_val[rt]+=x;
	chain_min[rt]+=x;
}
inline void son_add(int rt,ll x)
{
	son_min[rt]+=x;
	son_val[rt]+=x;
}
inline void point_add(int rt,ll x)
{
	val[rt]+=x;
	point_val[rt]+=x;
}
inline bool is_root(int rt)
{
	return rt!=s[f[rt]][0]&&rt!=s[f[rt]][1];
}
inline void splay_pushup(int rt)
{
	sum_size[rt]=sum_size[s[rt][0]]+sum_size[s[rt][1]]+sum_size[s[rt][2]];
	size[rt]=size[s[rt][0]]+size[s[rt][1]]+1;
	son_min[rt]=min(min(son_min[s[rt][0]],son_min[s[rt][1]]),min(son_min[s[rt][2]],chain_min[s[rt][2]]));
}
inline void LCT_pushup(int rt)
{
	sum_size[rt]=sum_size[s[rt][0]]+sum_size[s[rt][1]]+sum_size[s[rt][2]]+1;
	chain_min[rt]=min(min(chain_min[s[rt][0]],chain_min[s[rt][1]]),sum[rt]);
	son_min[rt]=min(min(son_min[s[rt][0]],son_min[s[rt][1]]),son_min[s[rt][2]]);
}
inline void splay_pushdown(int rt)
{
	if(son_val[rt])
	{
		son_add(s[rt][0],son_val[rt]);
		son_add(s[rt][1],son_val[rt]);
		son_add(s[rt][2],son_val[rt]);
		chain_add(s[rt][2],son_val[rt]);
		son_val[rt]=0;
	}
}
inline void LCT_pushdown(int rt)
{
	if(r[rt])
	{
		flip(s[rt][0]);
		flip(s[rt][1]);
		r[rt]^=1;
	}
	if(point_val[rt])
	{
		point_add(s[rt][0],point_val[rt]);
		point_add(s[rt][1],point_val[rt]);
		point_val[rt]=0;
	}
	if(chain_val[rt])
	{
		chain_add(s[rt][0],chain_val[rt]);
		chain_add(s[rt][1],chain_val[rt]);
		chain_val[rt]=0;
	}
	if(son_val[rt])
	{
		son_add(s[rt][0],son_val[rt]);
		son_add(s[rt][1],son_val[rt]);
		son_add(s[rt][2],son_val[rt]);
		son_val[rt]=0;
	}
}
inline void pushdown(int rt,int opt)
{
	if(f[rt])
	{
		if(rt==s[f[rt]][2])
		{
			pushdown(f[rt],opt^1);
		}
		else
		{
			pushdown(f[rt],opt);
		}
	}
	opt==0?LCT_pushdown(rt):splay_pushdown(rt);
}
inline void splay_rotate(int x)
{
	int rt=x;
	int fa=f[x];
	splay_pushdown(fa);
	splay_pushdown(rt);
	f[rt]=f[fa];
	if(f[fa])
	{
		is_root(fa)?s[f[fa]][2]=rt:s[f[fa]][get(fa)]=rt;
	}
	int k=(rt==s[fa][1]);
	link(fa,k,s[x][k^1]);
	link(rt,k^1,fa);
	splay_pushup(fa);
	splay_pushup(rt);
}
inline void LCT_rotate(int x)
{
	int rt=x;
	int fa=f[x];
	LCT_pushdown(fa);
	LCT_pushdown(rt);
	f[rt]=f[fa];
	if(f[fa])
	{
		is_root(fa)?s[f[fa]][2]=rt:s[f[fa]][get(fa)]=rt;
	}
	int k=(rt==s[fa][1]);
	link(fa,k,s[x][k^1]);
	link(rt,k^1,fa);
	LCT_pushup(fa);
	LCT_pushup(rt);
}
inline void splay_splay(int rt,int x=0)
{
	pushdown(rt,1);
	for(;!is_root(rt)&&f[rt]!=x;splay_rotate(rt))
	{
		if(!is_root(f[rt])&&f[f[rt]]!=x)
		{
			splay_rotate(get(rt)==get(f[rt])?f[rt]:rt);
		}
	}
}
inline void LCT_splay(int rt,int x=0)
{
	pushdown(rt,0);
	for(;!is_root(rt)&&f[rt]!=x;LCT_rotate(rt))
	{
		if(!is_root(f[rt])&&f[f[rt]]!=x)
		{
			LCT_rotate(get(rt)==get(f[rt])?f[rt]:rt);
		}
	}
}
inline int splay_find(int rt,int k)
{
	int x=rt;
	while(s[rt][k])
	{
		rt=s[rt][k];
	}
	splay_splay(rt,f[x]);
	return rt;
}
inline int LCT_find(int rt,int k)
{
	int x=rt;
	while(s[rt][k])
	{
		rt=s[rt][k];
	}
	LCT_splay(rt,f[x]);
	return rt;
}
inline bool binary_search(int rt,int k)//二分查找加点后这个子树的位置
{
	int num=rt;
	int now=rt;
	while(s[now][sum_size[s[now][2]]>k])
	{
		now=s[now][sum_size[s[now][2]]>k];
		if(sum_size[s[now][2]]==k)
		{
			num=now;
		}
	}
	splay_splay(num,f[rt]);
	return sum_size[s[num][2]]==k;
}
inline void change_structure(int rt)//修改树的结构
{
	LCT_splay(rt);
	while(f[rt])//调换子节点顺序
	{
		rt=f[rt];
		splay_splay(rt);
		if(s[rt][0]&&binary_search(s[rt][0],sum_size[s[rt][2]]))
		{
			swap(f[s[rt][2]],f[s[s[rt][0]][2]]);
			swap(s[rt][2],s[s[rt][0]][2]);
			rt=s[rt][0];
			splay_rotate(rt);
		}
		rt=f[rt];
		LCT_splay(rt);
		if(sum_size[s[s[rt][2]][2]]==sum_size[s[rt][1]])
		{
			swap(f[s[s[rt][2]][2]],f[s[rt][1]]);
			swap(s[s[rt][2]][2],s[rt][1]);
		}
		splay_pushup(s[rt][2]);
		LCT_pushup(rt);
	}
	if(!s[rt][0])
	{
		return ;
	}
	rt=LCT_find(rt,0);
	if(sum_size[rt]==2*sum_size[s[rt][1]])//移动重心
	{
		int x=s[rt][1];
		x=LCT_find(x,0);
		if(s[rt][2])
		{
			int y=s[rt][2];
			y=splay_find(y,0);
			link(rt,1,s[y][2]);
			link(rt,2,s[y][1]);
			LCT_pushup(rt);
		}
		else
		{
			s[rt][1]=0;
			LCT_pushup(rt);
		}
		if(s[x][1])
		{
			int y=build();
			link(y,1,s[x][2]);
			link(y,2,s[x][1]);
			splay_pushup(y);
			link(x,2,y);
		}
		link(x,1,rt);
		LCT_pushup(x);
		f[x]=0;
	}
}
inline void build_TopTree(int x,int anc)//建TopTree
{
	int len=q[x].size();
	for(int i=0;i<len;i++)
	{
		int v=to[q[x][i]];
		if(v!=anc)
		{
			build_TopTree(v,x);
			if(!s[root[x]][1])
			{
				link(root[x],1,root[v]);
			}
			else
			{
				int y=build();
				link(y,0,s[root[x]][2]);
				link(y,2,root[v]);
				splay_pushup(y);
				link(root[x],2,y);
			}
		}
	}
	val[root[x]]=sum[root[x]]=len;
	for(int i=0;i<len;i++)
	{
		val[root[x]]+=cost[q[x][i]]+1ll*i*sz[q[x][i]];
		sum[root[x]]+=cost[q[x][i]]+1ll*(i>>1)*sz[q[x][i]];
	}
	LCT_pushup(root[x]);
}
inline ll chain_partation(int fa,int rt)//链分治修改节点信息
{
	LCT_splay(fa);
	pushdown(fa,0);
	val[rt]=sum[rt]=val[fa]+1;
	LCT_pushup(rt);
	ll res=0;
	if(s[fa][1])
	{
		int x=build();
		link(x,0,s[fa][2]);
		link(x,2,rt);
		link(fa,2,x);
		rt=x;
		int rank=size[s[rt][0]]+1;
		if(s[f[rt]][0]||f[f[rt]])
		{
			rank++;
		}
		chain_add(s[rt][2],-rank);
		res+=rank;
		splay_pushup(rt);
		rt=f[rt];
		val[rt]++;
		sum[rt]+=rank/2+1-rank;
	}
	else
	{
		link(fa,1,rt);
		val[fa]+=(s[f[rt]][0]||f[f[rt]]);
		chain_add(rt,-1);
		res++;
		rt=fa;
	}
	point_add(s[rt][0],1);
	son_add(s[rt][0],1);
	LCT_pushup(rt);
	while(f[rt])
	{
		rt=f[rt];
		splay_splay(rt);
		LCT_splay(f[rt]);
		int rank=size[s[rt][0]]+1;
		if(s[f[rt]][0]||f[f[rt]])
		{
			rank++;
		}
		son_add(s[rt][1],1);
		chain_add(s[rt][2],1-rank);
		son_add(s[rt][2],1-rank);
		res+=rank-1;
		splay_pushup(rt);
		rt=f[rt];
		val[rt]++;
		sum[rt]+=rank/2+1-rank;
		point_add(s[rt][0],1);
		son_add(s[rt][0],1);
		LCT_pushup(rt);
	}
	chain_add(rt,res);
	son_add(rt,res);
	if(s[rt][0])
	{
		rt=LCT_find(rt,0);
		val[rt]--;
		son_add(s[rt][2],-1);
		LCT_pushup(rt);
	}
	return min(chain_min[rt],son_min[rt]);
}
inline int get_root(int rt)
{
	if(q[rt].empty()||sz[q[rt][0]]*2<=size[1])
	{
		return rt;
	}
	return get_root(to[q[rt][0]]);
}
inline bool cmp(int x,int y)
{
	return sz[x]>sz[y];
}
inline void add(int x,int y)
{
	next[++tot]=head[x];
	head[x]=tot;
	to[tot]=y;
}
inline void dfs(int x,int anc)
{
	fa[x]=anc;
	size[x]=1;
	for(int i=head[x];i;i=next[i])
	{
		if(to[i]!=anc)
		{
			dfs(to[i],x);
			sz[i]=size[to[i]];
			size[x]+=size[to[i]];
		}
	}
}
inline void dfs_pushup(int x,int anc)//树形DP
{
	for(int i=head[x];i;i=next[i])
	{
		if(to[i]!=anc)
		{
			dfs_pushup(to[i],x);
			cost[i]+=sum_cost[to[i]];
			sum_cost[x]+=cost[i];
		}
	}
}
inline void dfs_pushdown(int x,int anc,ll value)//树形DP
{
	for(int i=head[x];i;i=next[i])
	{
		if(to[i]!=anc)
		{
			dfs_pushdown(to[i],x,value+sum_cost[x]-cost[i]+cost[i^1]);
		}
		else
		{
			cost[i]=value;
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	if(n!=1)
	{
		dfs(1,0);
		for(int now=1;now<=n;now++)
		{
			for(int i=head[now];i;i=next[i])
			{
				if(to[i]==fa[now])
				{
					sz[i]=n-size[now];
				}
				q[now].push_back(i);
			}
			sort(q[now].begin(),q[now].end(),cmp);
			ll res=q[now].size()-1;
			int len=q[now].size();
			for(int i=0;i<len-1;i++)
			{
				res+=1ll*i*sz[q[now][i]];
			}
			cost[q[now][len-1]^1]=res;
			for(int i=len-2;i>=0;i--)
			{
				res+=1ll*(sz[q[now][i+1]]-sz[q[now][i]])*i;
				cost[q[now][i]^1]=res;
			}
		}
		dfs_pushup(1,0);
		dfs_pushdown(1,0,0);
		ans=INF;
		for(int now=1;now<=n;now++)
		{
			ll res=q[now].size();
			int len=q[now].size();
			for(int i=0;i<len;i++)
			{
				res+=cost[q[now][i]]+1ll*(i>>1)*sz[q[now][i]];
			}
			ans=min(ans,res);
		}
		printf("%lld\n",ans);
	}
	else
	{
		printf("0\n");
	}
	scanf("%d",&m);
	int rot=get_root(1);
	memset(size,0,sizeof(size));
	for(int i=1;i<=n+m;i++)
	{
		root[i]=build();
	}
	build_TopTree(rot,0);
	while(m--)
	{
		scanf("%d",&x);
		change_structure(root[x]);
		printf("%lld\n",chain_partation(root[x],root[++n]));
	}
}