推棋子

一共n+1行。
第一行输入一个数n，表示结点个数。
第二行输入n个数 $a_1,a_2,a_3...a_n$ 表示编号为i的结点上的分数为 $a_i$ 。
第三行到第n+1行每行输入两个数 $u_i$ ， $v_i$ ，表示第 $u_i$ 号结点和第 $v_i$ 号结点有一条边。

共一行，两个数p，q，表示棋子初始位置在p号结点时，（牛牛的分数-牛妹的分数）最大，最大为q，q可能为负数。
如果符合条件的p有多个，则输出编号最小的那个点。

C++ 解法, 执行用时: 729ms, 内存消耗: 47352K, 提交时间: 2021-05-25 00:00:48

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#define MN 1000000
#define MM 2000000
typedef long long ll;
const ll INF = 1e18;

int n,a[MN+5];
int hd[MN+5],to[MM+5],nxt[MM+5];
ll f[MM+5],ans[MN+5];

void add(int u,int v){
	static int rn = 0;
	to[rn] = v;
	nxt[rn] = hd[u];
	hd[u] = rn++;
}

ll dfs1(int u,int fa){
	ll mx = -INF;
	for(int i=hd[u];~i;i=nxt[i]){
		if(to[i]==fa) continue;
		f[i] = dfs1(to[i],u);
		mx = std::max(mx,f[i]);
	}
	return a[u]-(mx==-INF?0:mx);
}

void dfs2(int u,int fa){
    ll mx[2] = {-INF,-INF};
	for(int i=hd[u];~i;i=nxt[i]){
		if(f[i]>=mx[0]){
			mx[1] = mx[0];
			mx[0] = f[i];
		}else if(f[i]>=mx[1]){
			mx[1] = f[i];
		}
	}
	for(int i=hd[u];~i;i=nxt[i]){
		if(to[i]==fa) continue;
		if(f[i]==mx[0])
			f[i^1] = a[u]-(mx[1]==-INF?0:mx[1]);
		else
			f[i^1] = a[u]-(mx[0]==-INF?0:mx[0]);
		dfs2(to[i],u);
	}
	ans[u] = (mx[0]==-INF?0:mx[0]);
}

int main(){
	memset(hd,0xff,sizeof(hd));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=2;i<=n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs1(1,0);
	dfs2(1,0);
	ll ansv = -1e18;
	int ansi = 0;
	for(int i=1;i<=n;i++){
		if(ans[i]>ansv){
			ansv = ans[i];
			ansi = i;
		}
	}
	printf("%d %lld\n",ansi,ansv);
}

详情