- 1 program repair(input, output);
- 2 const 3 inf = 123456789;
- 4 type 5 etype = record 6 t,
- next: longint;
- 7 w: int64;
- 8 end;
- 9
- var 10 b, e: array[0..500050] of etype;
- 11 father: array[0..500050, 0..20] of longint;
- 12 v: array[0..250025] of boolean;
- 13 a,
- d,
- head,
- q,
- dfn,
- fa: array[0..250025] of longint;
- 14 w,
- f: array[0..250025] of int64;
- 15 c: array[0..500050] of longint;
- 16 n,
- m,
- i,
- j,
- k,
- x,
- y,
- cnt,
- top,
- h,
- t,
- r: longint;
- 17 z: int64;
- 18 procedure add(x, y: longint; w: int64);
- 19 begin 20 inc(cnt);
- e[cnt].t: =y;
- e[cnt].w: =w;
- e[cnt].next: =a[x];
- a[x] : =cnt;
- 21 end;
- 22
- function min(a, b: int64) : int64;
- 23 begin 24
- if athen exit(a)
- else exit(b);
- 25 end;
- 26 procedure dfs(k: longint);
- 27
- var 28 i: longint;
- 29 begin 30 inc(cnt);
- dfn[k] : =cnt;
- if d[k] > r then r: =d[k];
- 31 i: =a[k];
- 32
- while i < >0 do 33 begin 34
- if dfn[e[i].t] = 0 then 35 begin 36 father[e[i].t, 0] : =k;
- d[e[i].t] : =d[k] + 1;
- w[e[i].t] : =min(w[k], e[i].w);
- 37 dfs(e[i].t);
- 38 end;
- 39 i: =e[i].next;
- 40 end;
- 41 end;
- 42 procedure sort(q, h: longint);
- 43
- var 44 i, j, x, t: longint;
- 45 begin 46 i: =q;
- j: =h;
- x: =dfn[c[(i + j) >> 1]];
- 47 repeat 48
- while dfn[c[i]] do inc(i);
- 49
- while xdo dec(j);
- 50
- if i <= j then 51 begin 52 t: =c[i];
- c[i] : =c[j];
- c[j] : =t;
- 53 inc(i);
- dec(j);
- 54 end;
- 55 until i > j;
- 56
- if j > q then sort(q, j);
- 57
- if ithen sort(i, h);
- 58 end;
- 59
- function lca(x, y: longint) : longint;
- 60
- var 61 t: longint;
- 62 begin 63
- if d[x] then begin t: =x;
- x: =y;
- y: =t;
- end;
- 64
- for k: =r downto 0 do
- if d[father[x, k]] >= d[y] then x: =father[x, k];
- 65
- if x = y then exit(x);
- 66
- for k: =r downto 0 do
- if father[x, k] < >father[y, k] then begin x: =father[x, k];
- y: =father[y, k];
- end;
- 67 exit(father[x, 0]);
- 68 end;
- 69 procedure ins(x, y: longint);
- 70 begin 71 inc(cnt);
- b[cnt].t: =y;
- b[cnt].next: =head[x];
- head[x] : =cnt;
- 72 end;
- 73 begin 74 assign(input, 'repair. in ');
- assign(output, 'repair.out');
- reset(input);
- rewrite(output);
- 75 readln(n);
- cnt: =0;
- 76 fillchar(a, sizeof(a), 0);
- 77
- for i: =2 to n do begin read(x, y, z);
- add(x, y, z);
- add(y, x, z);
- end;
- 78 fillchar(dfn, sizeof(dfn), 0);
- cnt: =0;
- father[1, 0] : =0;
- d[1] : =1;
- 79
- for i: =1 to n do w[i] : =inf;
- r: =0;
- 80 dfs(1);
- 81 k: =0;
- i: =1;
- 82
- while ido begin i: =i + i;
- inc(k);
- end;
- 83 r: =k;
- 84
- for j: =1 to r do
- for i: =1 to n do father[i, j] : =father[father[i, j - 1], j - 1];
- 85 readln(m);
- 86 fillchar(head, sizeof(head), 0);
- fillchar(v, sizeof(v), false);
- fillchar(f, sizeof(f), 0);
- 87
- for i: =1 to m do 88 begin 89 read(x);
- for j: =1 to x do begin read(c[j]);
- v[c[j]] : =true;
- end;
- 90 sort(1, x);
- y: =x;
- 91
- for j: =2 to x do begin inc(y);
- c[y] : =lca(c[j], c[j - 1]);
- if c[y] = 1 then dec(y);
- end;
- 92 sort(1, y);
- x: =1;
- 93
- for j: =2 to y do
- if c[j] < >c[j - 1] then begin inc(x);
- c[x] : =c[j];
- end;
- 94 top: =1;
- q[1] : =1;
- cnt: =0;
- 95
- for j: =1 to x do 96 begin 97
- while lca(q[top], c[j]) < >q[top] do dec(top);
- 98 fa[c[j]] : =q[top];
- ins(q[top], c[j]);
- 99 inc(top);
- q[top] : =c[j];
- 100 end;
- 101 h: =0;
- t: =1;
- q[1] : =1;
- 102
- while hdo 103 begin 104 inc(h);
- 105 j: =head[q[h]];
- 106
- while j < >0 do begin inc(t);
- q[t] : =b[j].t;
- j: =b[j].next;
- end;
- 107 end;
- 108
- for j: =x + 1 downto 2 do 109 begin 110
- if (w[q[j]] or v[q[j]] then f[q[j]] : =w[q[j]]; 111 inc(f[fa[q[j]]], f[q[j]]); 112 end; 113 writeln(f[1]); 114
- for j: =1 to x do begin v[c[j]] : =false; f[c[j]] : =0; head[c[j]] : =0; end; f[1] : =0; head[1] : =0; 115 end; 116 close(input); close(output); 117 end.
来源: http://www.bubuko.com/infodetail-1995265.html