一开始以为是个树形dp，特地去学了。。结果是个思维题
/* 树结构，设最大点权值为Max,则答案必在在区间[Max,Max+2] 证明ans <= Max+2 任取一个点作为根节点，那么去掉这个点之后其儿子结点，孙子结点的权值+1，同理，每去掉一个点之后其儿子结点，孙子结点的权值都会加上1 即每个点的权值最多只能被+2，即它的父亲，爷爷结点会导致其增加权值 考虑什么时候ans=Max:只有一个Max结点，以其为根，若有权值Max-1的点，那么这些点只有一个父亲就是Max ans=Max+1:所有的Max有相同的父亲 怎么判断 */ #include<bits/stdc++.h> using namespace std; #define maxn 300005 struct Edge{ int to,next; }edge[maxn<<2]; int head[maxn],tot,n,a[maxn]; void init(){ memset(head,-1,sizeof head); tot=0; } void addedge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int main(){ int Max=-1000000007,tot1=0,tot2=0,u,v,x; init(); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); Max=max(Max,a[i]); } for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } for(int i=1;i<=n;i++) if(Max==a[i]) tot1++,u=i; else if(Max-1==a[i]) tot2++; int tmp=0; if(tot1==1){//只有一个Max for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(a[v]==Max-1)tmp++; } if(tmp==tot2)//所有Max-1都是其子节点 printf("%d",Max); else printf("%d",Max+1); return 0; } int vis[maxn]={},flag=0; queue<int>q; q.push(1);vis[1]=1; while(!q.empty()){ int u=q.front();q.pop();vis[u]=1; int tmp=a[u]==Max?1:0; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(!vis[v]) q.push(v); if(a[v]==Max)tmp++; } if(tmp==tot1){ flag=1;break; } } if(flag) printf("%d",Max+1); else printf("%d",Max+2); }