gym100796C(想法题／二分+树形dp)

Bob's new favourite toy is a rooted tree that consists of n vertices numbered from 1 to n. The number of the root vertex is 1. The tree has l leafs (the root is not considered to be a leaf). Each leaf of the tree has an integer written in it.

This birthday Bob received n - l stickers as a gift: k of them are labelled "min", and the other n - l - k are labelled "max". Bob has decided to place the stickers on the internal vertices of the tree, a single sticker on each internal vertex.

Once he has placed all the stickers on the tree, Bob would like to calculate a function f for each vertex v of the tree in the following fashion: 

Bob isn't yet sure how to place his stickers on the tree, but he is interested in the value of f in the root vertex. Given the tree and the stickers, help Bob calculate the minimum and the maximum possible value of f(1)!

The first line contains two space-separated integers n and k (2 ≤ n ≤ 105, 0 ≤ k ≤ n). The second line contains n - 1 space-separated integer numbers p2, p3, ..., pn (1 ≤ pi ≤ n). The number pi denotes the parent of the vertex numbered i. The third line contains n space-separated integer numbers a1, a2, ..., an (0 ≤ ai ≤ 109). If the vertex i is a leaf, then ai is the number written in that vertex. Otherwise aiwill be equal to 0.

It is guaranteed that the given graph will be a tree. It is guaranteed that k + l ≤ n.

In a single line output two integers separated by a space — the minimum and the maximum possible value of f(1).

6 11 1 2 2 30 0 0 1 3 2output
2 3Note
A tree is a connected graph that has no cycles. A rooted tree is a tree with one vertex being the root vertex. In a rooted tree, a vertex u is a child of v if and only if there is an edge between v and u, and u does not belong to the path that connects the root vertex with v. The vertex v then is called the parent of u. A vertex of a rooted tree is called a leaf if and only if it has no children. Otherwise the vertex is called an internal vertex.
题解：
刚开始看完题就觉得弱当前结点称为最小值，那么就是需要deep-1个min tag。
然后发现样例就不对
其实样例提供了一个坑，若一个点只有一个儿子，那么dfs的时候deep就不用+1了。
然后一次dfs就能解决。
#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>using namespace std;const int MAXN=200010;const int INF=1000000007;int p[MAXN];int a[MAXN];int son[MAXN]={0};struct node{	int v,next;};node G[MAXN];int head[MAXN];int is_leaf[MAXN]={0};int tot=0;void add(int u,int v){	G[tot].v=v;	G[tot].next=head[u];	head[u]=tot++;}int M1=0,M2=INF;int MIN[MAXN],MAX[MAXN];int n,k;int l=0;void dfs(int u,int deep){	for(int k=head[u];k!=-1;k=G[k].next){		int v=G[k].v;		if(son[u]==1){			dfs(v,deep);		}		else{			dfs(v,deep+1);		}		MAX[u]=max(MAX[u],MAX[v]);		MIN[u]=min(MIN[u],MIN[v]);	}	if(deep-1<=k){		M2=min(M2,MAX[u]);	}	if(deep-1<=n-k-l){		M1=max(M1,MIN[u]);	}	return;}int main(int argc, char *argv[]) {	memset(head,-1,sizeof(head));	memset(p,0,sizeof(p));	memset(MAX,0,sizeof(MAX));	memset(MIN,INF,sizeof(MIN));	scanf("%d%d",&n,&k);	for(int i=2;i<=n;i++){		scanf("%d",&p[i]);		add(p[i],i);		son[p[i]]++;	}	for(int i=1;i<=n;i++){		scanf("%d",&a[i]);		if(a[i]){			MAX[i]=MIN[i]=a[i];			l++;		}	}	dfs(1,1);	PRintf("%d %d/n",M2,M1);}
其实也可以变为判定性问题，假设最小值小于等于x，那么就用树形dp判断一下至少需要多少个min tag，判断数量和k的关系得出其是否可行。二分x即可。
不过这个树形dp还是比较坑的，wa了好久。。。
假设f[i]为以i为根的子树最少需要多少个tag，如果结点只有一个儿子，那么就是那个儿子的f的值，如果所有儿子值都为0，那么f[i]也是0，如果所有儿子值都大于inf(表示不可能),那么f[i]也为inf，否者为min(f[i的儿子])+1.
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef unsigned long long ll;typedef pair<int,int> PII;const int inf=1e9+100;const ll mod=1000000007;const int maxn=1e5+100;int head[maxn];struct edge{    int from,to,next;}e[maxn];   //int tol=0;void add(int u,int v){    e[++tol].to=v,e[tol].next=head[u],head[u]=tol;}ll f[maxn];int a[maxn];int n,k;bool flag;ll dfs1(int u,int v){    if(a[u])    {        if(flag)            return a[u]<=v? 0:inf;        else            return a[u]>=v? 0:inf;    }    else    {        ll tot=0,mi=inf,mx=0;;        int cnt=0,cnt1=0;        for(int i=head[u];i;i=e[i].next)        {            int vv=e[i].to;            ll p=dfs1(vv,v);            if(p) cnt++;            cnt1++;            tot+=p;            mi=min(mi,p);            mx=max(mx,p);        }        if(mi>=inf) return inf;        if(cnt==0) return 0;        if(cnt1==1) return mi;        else return mi+1;    }}bool check1(int x){    return dfs1(1,x)<=k;    }int main(){    scanf("%d%d",&n,&k);    rep(i,2,n+1)    {        int p;        scanf("%d",&p);        add(p,i);    }    int c=0;    rep(i,1,n+1)    {        scanf("%d",&a[i]);        if(a[i]) c++;  //    }    int ans=-1;    int l=-1,r=1e9+10;    flag=true;    while(l<=r)    {        int mid=(l+r)/2;        if(check1(mid)) ans=mid,r=mid-1;        else l=mid+1;    }    printf("%d ",ans);    k=n-c-k;    flag=false;    l=-1,r=1e9+10;    while(l<=r)    {        int mid=(l+r)/2;        if(check1(mid)) ans=mid,l=mid+1;        else r=mid-1;    }    printf("%d/n",ans);    return 0;}