Description：

给一棵树，走过每条边需要花费一个时间，安装软件又需要花费一个时间，需要遍历整棵树并回到起点，想让所有点中到达时间+安装时间的最大值最小，问这个值是多少。

$1\le n \le 500000$

Solution：

设 $f[i]$ 表示点 $i$ 及其子树都装好软件的最短时间，对于每个非叶子节点，设他的两个儿子分别是 $a$ 和 $b$ ，那么先进 $a$ 的时间为 $\max(f[a]+1,siz[a]\times2+f[b]+1)$ ，先进 $b$ 的时间为 $\max(f[b]+1,siz[b]\times2+f[a]+1)$ ，之所以加一是因为 $c_i\ge 1$ ，所以回来就不算了，要想先进 $a$ 就要让 $\max(f[a]+1,siz[a]\times2+f[b]+1)<\max(f[b]+1,siz[b]\times2+f[a]+1)$ ，有了国王游戏的经验发现这其实就是 $f[a]-siz[a]\times2>f[b]-siz[b]\times2$ ，按照这个给每个点的子树排序即可。 $f[]$ 就是上面那个值 $+$ 安装软件的时间。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n;

#define MAXN 500010

int val[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

struct node{int siz,f;};

bool vis[MAXN];

int siz[MAXN];

int f[MAXN];

bool cmp(node a,node b){return a.f - a.siz * 2 > b.f - b.siz * 2;}

void dfs(int k)

{

	siz[k] = 1;vis[k] = true;

	vector<node> v;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dfs(e[i].to);

		v.push_back((node){siz[e[i].to],f[e[i].to]});

		siz[k] += siz[e[i].to];

	}

	sort(v.begin(),v.end(),cmp);

	int s = 0;

	f[k] = 0;

	for(vector<node>::iterator i = v.begin();i != v.end();++i)

	{

		f[k] = max(f[k],s * 2 + i -> f + 1);

		s += i -> siz;

	}

	f[k] = max(f[k],val[k]);

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)val[i] = read();

	int a,b;

	for(int i = 1;i < n;++i)

	{

		a = read();b = read();

		add(a,b);

	}

	int tmp = val[1];

	dfs(1);

	cout << max(f[1],2 * (n - 1) + tmp) << endl;

	return 0;

}