gym100796C(想法题／二分+树形dp)-白红宇的个人博客

发布日期：2021-11-12 00:25:44 浏览次数：3 分类：技术文章

本文共 5202 字，大约阅读时间需要 17 分钟。

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:

If v is a leaf, f(v) is equal to the integer that is written in v.

If v has a "min" sticker, f(v) is equal to the minimum value of f(u), where u is any child of v.

If v has a "max" sticker, f(v) is equal to the maximum value of f(u), where u is any child of v.

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)!

Input

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.

Output

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

     Examples 
       input 
6 11 1 2 2 30 0 0 1 3 2
       output 
2 3

Note

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 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        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
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define rep(i,a,n) for (int i=a;i
          
           =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
           
             VI;typedef unsigned long long ll;typedef pair
            
              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;}

转载地址：https://blog.csdn.net/fouzhe/article/details/55547950 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：gym100812G(想法题,最短路变形,好题)

下一篇：AIM Tech Round (Div. 1) B. Array GCD(数论+dp)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章