2756 樹上的路徑
?時間限制: 3 s ?空間限制: 128000 KB ?題目等級 : 大師 Master
題目描述?Description
給出一棵樹，求出最小的k，使得，且在樹中存在路徑P，使得k>= S 且 k <=E. （k為路徑P上的邊的權值和）
輸入描述?Input Description
第一行給出N，S，E，N代表樹的點數，S，E如題目描述一致
下面N-1行給出這棵樹的相鄰兩個節點的邊及其權值W
輸出描述?Output Description
輸出一個整數k，表示存在路徑P,并且路徑上的權值和 K>=S , k<=E，若無解輸出-1
樣例輸入?Sample Input
5 10 40
2 4 80
2 3 57
1 2 16
2 5 49
樣例輸出?Sample Output
16
數據范圍及提示?Data Size & Hint
邊權W<=10000,
保證答案在int（longint）范圍內,且|E-S|<=50，
樹上點的個數N<=30000
??
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define N 30009 6 using namespace std; 7 int n,A,B,K,la,head[N],next[N<<1],ans=2*1e9,size[N]; 8 int dep[N],maxson[N],root,tot,lls,num,ls[N]; 9 bool v[N]; 10 struct node 11 { 12 int fr,to,len; 13 }a[N<<1]; 14 void addedge(int x,int y,int z) 15 { 16 a[++la].fr=x,a[la].to=y,a[la].len=z; 17 next[la]=head[x],head[x]=la; 18 } 19 void get_root(int x,int from) 20 { 21 size[x]=1; 22 maxson[x]=0; 23 for(int i=head[x];i;i=next[i]) 24 if (!v[ a[i].to ]&&a[i].to!=from) 25 { 26 get_root(a[i].to,x); 27 size[x]+=size[ a[i].to ]; 28 maxson[x]=max(maxson[x],size[ a[i].to ]); 29 } 30 maxson[x]=max( maxson[x],tot-size[x] ); 31 if (!root||maxson[x]<maxson[root]) root=x; 32 33 } 34 void get_dep(int x,int from) 35 { 36 for (int i=head[x];i;i=next[i]) 37 if (!v[ a[i].to ]&&a[i].to!=from) 38 { 39 ls[++lls]=dep[ a[i].to ]=dep[x]+a[i].len; 40 get_dep(a[i].to,x); 41 42 } 43 } 44 int get_num(int x,int jian) 45 { 46 int i,j,k,rt=0; 47 ls[ lls=1 ]=dep[x]=jian; 48 get_dep(x,0); 49 50 sort(ls+1,ls+lls+1); 51 for (i=1,j=lls;i<=lls;i++) 52 { 53 while (j>1&&ls[i]+ls[j]>K) j--; 54 if (j>i)rt+=j-i; 55 } 56 return rt; 57 } 58 void divide(int x) 59 { 60 num+=get_num(x,0); 61 v[x]=1; 62 for (int i=head[x];i;i=next[i]) 63 if (!v[ a[i].to ]) 64 { 65 num-=get_num(a[i].to,a[i].len); 66 tot=size[ a[i].to ]; 67 root=0,get_root(a[i].to,0); 68 divide( root ); 69 } 70 } 71 int main() 72 { 73 int i,j,k,x,y,z,last; 74 scanf("%d%d%d",&n,&A,&B); 75 for(i=1;i<n;i++) 76 { 77 scanf("%d%d%d",&x,&y,&z); 78 addedge(x,y,z),addedge(y,x,z); 79 } 80 last=1e9; 81 for(K=A-1;K<=B;K++) 82 { 83 num=0; 84 memset(v,0,sizeof(v)); 85 tot=n,root=0; 86 get_root(1,0); 87 divide(root); 88 if(num>last) 89 { 90 printf("%d\n",K); 91 return 0; 92 } 93 last=num; 94 } 95 printf("-1\n"); 96 }
?備注：引用自Codevs 題解
字節流練習)
