题意：给你一棵树，你可以选择开始的根和遍历儿子的顺序，求按照选定顺序的dfs遍历的前k个点的min{ai}最大。
标程：
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=200005; 5 int n,cnt,head[N],fa[N],sz[N],k,Max,f[N],a[N],u,v,l,r,size[N],ans,b[N]; 6 struct node{int to,next;}num[N*2]; 7 void add(int x,int y) 8 {num[++cnt].to=y;num[cnt].next=head[x];head[x]=cnt;} 9 void dfs_pre(int x) 10 { 11 sz[x]=1; 12 for (int i=head[x];i;i=num[i].next) 13 if (num[i].to!=fa[x]) 14 { 15 fa[num[i].to]=x; 16 dfs_pre(num[i].to); 17 sz[x]+=sz[num[i].to]; 18 } 19 } 20 void dfs(int x,int mid) 21 { 22 size[x]=(a[x]>=mid);int ans=1,mx=0,mxc=0; 23 for (int i=head[x];i;i=num[i].next) 24 if (num[i].to!=fa[x]) 25 { 26 dfs(num[i].to,mid); 27 size[x]+=size[num[i].to]; 28 if (size[num[i].to]==sz[num[i].to]) ans+=sz[num[i].to]; 29 else if (f[num[i].to]>mx) mxc=mx,mx=f[num[i].to]; 30 else if (f[num[i].to]>mxc) mxc=f[num[i].to]; 31 } 32 if (a[x]<mid) f[x]=0;else f[x]=ans+mx; 33 if (cnt-size[x]==n-sz[x]) ans+=n-sz[x];//这里不能用size[1]，因为还没处理啊 34 if (a[x]>=mid) Max=max(Max,ans+mx+mxc); 35 } 36 bool check(int mid) 37 { 38 Max=0;cnt=lower_bound(b+1,b+n+1,mid)-b-1;cnt=n-cnt; 39 dfs(1,mid); 40 return Max>=k; 41 } 42 int main() 43 { 44 scanf("%d%d",&n,&k); 45 for (int i=1;i<=n;i++) scanf("%d",&a[i]),Max=max(Max,a[i]),b[i]=a[i]; 46 for (int i=1;i<n;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u); 47 sort(b+1,b+n+1); 48 dfs_pre(1); 49 l=1;r=ans=Max; 50 while (l<=r) 51 { 52 int mid=(l+r)>>1; 53 if (check(mid)) ans=mid,l=mid+1;else r=mid-1; 54 } 55 printf("%d ",ans); 56 return 0; 57 }
易错点：1.这里不能用size[1]，因为还没处理啊。所以用一个lower_bound算有多少个数>=mid。
题解：二分答案+树形dp
答案显然有可二分性，对于一个mid，将>=mid的点标黑。
check就是找到一段连续dfs序的点问是否>=k。
枚举每一个点统计根在其子树中的答案，找其子树中有多少个满块（可以遍历满），以及最大和次大的非满块。
而对于其子树外的那一块，只用考虑其为满块的情况。（如果不是满块，那么可以追溯到该点到根的链上的另一点，该点满足子树外的满，或是走不下去。那时这种情况会被统计。）
那么答案就是当当前点为黑点时，满块+最大+次大+1（当前点）。根不一定是当前点，而是从非满块的一个端点开始。