There is a rooted tree with $N$ vertices, Vertex $1$ being the root.
For each $i = 1, 2, \ldots, N-1$, the $i$-th edge connects Vertex $u_i$ and Vertex $v_i$.
Each vertex other than the root has a positive integer written on it: for each $i = 2, 3, \ldots, N$, the integer written on Vertex $i$ is $A_i$.
Takahashi and Aoki will use this rooted tree and a piece to play the following game against each other. The piece starts on Vertex $1$. Until the game ends, they repeat the following procedure. At the end of the game, Takahashi's score will be the integer written at that time on the vertex the piece is on.
Takahashi wants to make his score as large as possible, while Aoki wants to make it as small as possible.
Print the score Takahashi will get when both players play optimally for their respective purposes.Problem Statement
Constraints
Input
Input is given from Standard Input in the following format:
$N$
$A_2$ $\ldots$ $A_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
Output
Print the answer.
Sample Input 1
7 2 4 6 5 6 10 1 2 1 3 2 4 2 5 5 6 5 7
Sample Output 1
5
Here is a possible progression of the game when both players play optimally.
- The piece starts on Vertex $1$.
- Aoki changes the integer written on Vertex $7$ from $10$ to $0$.
- Takahashi moves the piece from Vertex $1$ to Vertex $2$.
- Aoki changes the integer written on Vertex $4$ from $6$ to $0$.
- Takahashi moves the piece from Vertex $2$ to Vertex $5$.
- Takahashi chooses to end the game.
At the end of the game, the piece is on Vertex $5$, on which the integer $5$ is written at that time, so Takahashi's score will be $5$.
Sample Input 2
30 29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62 32 38 84 49 93 53 26 13 25 13 15 14 22 17 24 12 3 4 3 5 8 26 15 3 2 2 9 4 25 4 13 2 10 28 15 6 4 2 5 19 9 2 7 2 14 23 30 17 2 7 16 21 13 13 23 13 20 1 2 6 18 27 6 21 29 11 8
Sample Output 2
70
首先发现如果 Aoki 漫无目的地操作，是难以移到好的地方的。所以我们可以通过二分来给他定一个目标。
设现在二分出来 Aoki 的目标是 \(x\) 分，那么所有大于等于 \(x\) 的节点都要在 Takahashi 到达这个点之前被 Aoki 删掉。那么我们记录 \(dp_i\) 为如果要使以 \(i\) 为根的子树满足要求，需要 \(i\) 上面的点多帮忙删几个点。那么\(dp_i=\max((\sum\limits_{j\in son}dp_j) -1,0)+(a[i]>t)\)。最终判断 \(dp_i\) 是否为 \(0\) 即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a[N],u,v,hd[N],e_num,l,r;
struct edge{
int v,nxt;
}e[N<<1];
void add_edge(int u,int v)
{
e[++e_num]=(edge){v,hd[u]};
hd[u]=e_num;
}
int dfs(int x,int y,int t)
{
int ret=0;
for(int i=hd[x];i;i=e[i].nxt)
if(e[i].v!=y)
ret+=dfs(e[i].v,x,t);
return max(ret-1,0)+(a[x]>t);
}
int check(int x)
{
return dfs(1,0,x)==0;
}
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++)
scanf("%d",a+i);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
l=0,r=1e9+1;
while(l<=r)
{
int md=l+r>>1;
if(check(md))
r=md-1;
else
l=md+1;
}
printf("%d",l);
}