Codeforces Round #701 (Div. 2) E. Move and Swap

　　注意到 “The leaves are all at the same distance d from the root.”

　　且 red coin 影响后续操作 blue coin 不影响.

　　设 f[x] 表示 red coin 到 节点 x 其以下层操作完毕的最大差值和

　　且 y = fa[x] u 是与 x 同层的任意节点

　　则 f[y] = max(f[x]+|a[x]-a[u]|(1), f[u]+|a[u]-a[x]|(2))

　　(1)：x 这一层不交换

　　(2)：x 这一层交换

　　维护 max(f[x]+a[x]) max(f[x]-a[x]) max(a[x]) max(-a[x]) 即可

　　时间复杂度 O(n)

#include

using namespace std;

#define inf 1ll*100000000000000000
#define N 200005
#define LL long long

int t, n, i, Q[N], vis[N], d[N], D,  x, fa[N];
LL f[N], a[N];
vector G[N], A[N];

void add(int x,int y)
{
	G[x].push_back(y);
}

void BFS(int S)
{
	int x, y, h, t, i;
	LL M1, M2, M3, M4, cur;
	
	for (i=1; i<=n; i++) vis[i]=0;
	Q[1]=S; vis[S]=1; d[S]=0; h=0,t=1;
	for (; h