首页 > 其他 > 详细

zxa and leaf

时间:2019-03-20 00:19:42      阅读:64      评论:0      收藏:0      [点我收藏+]

标签:otto   ble   other   alt   one   lease   main   scanf   ann   

zxa and leaf

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 502    Accepted Submission(s): 198


Problem Description
zxa have an unrooted tree with n技术分享图片 nodes, including (n1)技术分享图片 undirected edges, whose nodes are numbered from 1技术分享图片 to n技术分享图片 . The degree of each node is defined as the number of the edges connected to it, and each node whose degree is 1技术分享图片 is defined as the leaf node of the tree.

zxa wanna set each node‘s beautiful level, which must be a positive integer. His unrooted tree has m(1mn)技术分享图片 leaf nodes, k(1km)技术分享图片 leaf nodes of which have already been setted their beautiful levels, so that zxa only needs to set the other nodes‘ beautiful levels.

zxa is interested to know, assuming that the ugly level of each edge is defined as the absolute difference of the beautiful levels between two nodes connected by this edge, and the ugly level of the tree is the maximum of the ugly levels of **all the edges on this tree**, then what is the minimum possible ugly level of the tree, can you help him?
 

 

Input
The first line contains an positive integer T技术分享图片 , represents there are T技术分享图片 test cases.

For each test case:

The first line contains two positive integers n技术分享图片 and k技术分享图片 , represent the tree has n技术分享图片 nodes, k技术分享图片 leaf nodes of which have already been setted their beautiful levels.

The next (n1)技术分享图片 lines, each line contains two distinct positive integers u技术分享图片 and v技术分享图片 , repersent there is an undirected edge between node u技术分享图片 and node v技术分享图片 .

The next k技术分享图片 lines, each lines contains two positive integers u技术分享图片 and w技术分享图片 , repersent node u技术分享图片 is a leaf node, whose beautiful level is w技术分享图片 .

There is a blank between each integer with no other extra space in one line.

It‘s guaranteed that the input edges constitute a tree.

1T10,2n510技术分享图片4技术分享图片,1kn,1u,vn,1w10技术分享图片9技术分享图片技术分享图片
 

 

Output
For each test case, output in one line a non-negative integer, repersents the minimum possible ugly level of the tree.
 

 

Sample Input
2 3 2 1 2 1 3 2 4 3 9 6 2 1 2 1 3 1 4 2 5 2 6 3 6 5 9
 

 

Sample Output
3 1
Hint
If you need a larger stack size, please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.
 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=1e5+10;
struct node{
     int to,nx;
}p[maxn];
int T,n,k,head[maxn],vis[maxn],tot,d[maxn];
ll small[maxn],big[maxn],val[maxn];
void addedge(int u,int v){
       p[++tot].to=v,p[tot].nx=head[u],head[u]=tot;
}
bool dfs(int now,int fa,int w){
      for(int i=head[now];i;i=p[i].nx){
            int to=p[i].to;
            if(to==fa)continue;
            if(!dfs(to,now,w))return false;
            ll tempsmall=small[to]-w;
            ll tempbig=big[to]+w;
            if(tempsmall>big[now]||tempbig<small[now])return false;
            small[now]=max(small[now],tempsmall);
            big[now]=min(big[now],tempbig);
      }
      return true;
}
bool ok(int cur,int root){
      for(int i=1;i<=n;i++){
           if(vis[i])continue;
           small[i]=-0x3f3f3f3f;
           big[i]=0x3f3f3f3f;
      }
      if(dfs(root,-1,cur))return true;
      else return false;
}
int main()
{
    scanf("%d",&T);
    while(T--){
        tot=0;
        scanf("%d%d",&n,&k);
        memset(d,0,sizeof(d));
        memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(small,0,sizeof(small));
        memset(big,0,sizeof(big));
        for(int i=1;i<=n-1;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            addedge(a,b);
            addedge(b,a);
            d[a]++,d[b]++;
        }
        while(k--){
            int a,b;
            scanf("%d%d",&a,&b);
            small[a]=big[a]=b;
            vis[a]=1;
        }
        int root=1;
        for(int i=1;i<=n;i++){
            if(!d[i]){
                root=i;
                break;
            }
        }
        int l=0,r=0x3f3f3f3f;
        while(l<=r){
            int mid=l+r>>1;
            if(ok(mid,root))r=mid-1;
            else l=mid+1;
        }
        cout<<l<<endl;
    }
    return 0;
}

 

zxa and leaf

标签:otto   ble   other   alt   one   lease   main   scanf   ann   

原文:https://www.cnblogs.com/czy-power/p/10562375.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号