赣州晒房网门户网站,网站地图怎么用,做燕鲍翅的网站,免费h5网站模版2756 树上的路径 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 大师 Master题目描述 Description给出一棵树#xff0c;求出最小的k#xff0c;使得#xff0c;且在树中存在路径P#xff0c;使得k S 且 k E. #xff08;k为路径P上的边的权值和求出最小的k使得且在树中存在路径P使得k S 且 k E. k为路径P上的边的权值和 输入描述 Input Description 第一行给出NSEN代表树的点数SE如题目描述一致 下面N-1行给出这棵树的相邻两个节点的边及其权值W 输出描述 Output Description 输出一个整数k表示存在路径P,并且路径上的权值和 KS , kE若无解输出-1 样例输入 Sample Input 5 10 40 2 4 80 2 3 57 1 2 16 2 5 49 样例输出 Sample Output 16 数据范围及提示 Data Size Hint 边权W10000, 保证答案在intlongint范围内,且|E-S|50 树上点的个数N30000 1 #includeiostream2 #includecstdio3 #includecstring4 #includealgorithm5 #define N 300096 using namespace std;7 int n,A,B,K,la,head[N],next[N1],ans2*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[N1];
14 void addedge(int x,int y,int z)
15 {
16 a[la].frx,a[la].toy,a[la].lenz;
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 ihead[x];i;inext[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]) rootx;
32
33 }
34 void get_dep(int x,int from)
35 {
36 for (int ihead[x];i;inext[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,rt0;
47 ls[ lls1 ]dep[x]jian;
48 get_dep(x,0);
49
50 sort(ls1,lslls1);
51 for (i1,jlls;ills;i)
52 {
53 while (j1ls[i]ls[j]K) j--;
54 if (ji)rtj-i;
55 }
56 return rt;
57 }
58 void divide(int x)
59 {
60 numget_num(x,0);
61 v[x]1;
62 for (int ihead[x];i;inext[i])
63 if (!v[ a[i].to ])
64 {
65 num-get_num(a[i].to,a[i].len);
66 totsize[ a[i].to ];
67 root0,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(i1;in;i)
76 {
77 scanf(%d%d%d,x,y,z);
78 addedge(x,y,z),addedge(y,x,z);
79 }
80 last1e9;
81 for(KA-1;KB;K)
82 {
83 num0;
84 memset(v,0,sizeof(v));
85 totn,root0;
86 get_root(1,0);
87 divide(root);
88 if(numlast)
89 {
90 printf(%d\n,K);
91 return 0;
92 }
93 lastnum;
94 }
95 printf(-1\n);
96 } 备注引用自Codevs 题解 转载于:https://www.cnblogs.com/suishiguang/p/6172038.html
