BZOJ

BZOJ 2286

我说这傻逼题我™改了一整天你信么…

传送门

一大早回忆了一下老早之前看过的虚树写法…到了机房开始敲

敲了一个小时发现过不了样例于是找了个BUG，改了一会过了样例和对拍

发现稍微大一点的数据跑起来就像吃了*一样 咦为什么还没有暴力快，然后回头瞅了瞅代码

发现我这个傻逼干了这些事情：

  • 每次建虚树的函数中开了个250000大小的数组（此函数最多会调用250000次）
  • 每次把好几个250000大小的数组fillchar

改对了以后马上交了一发TLE = =

要来数据开始测 卧槽本地21S+

卡了半天常…还写了我人生中第一发RMQ求LCA 按理说比倍增快不了多少啊

还尼玛TLE

去膜hzwer的代码，发现一个貌似能优化的东东，加上去之后继续T…（此时已到午饭点）

下午又卡了半天常无果，求助身边神犇被D一脸是自己写法有问题

不管怎么改依旧本地压线过交上去毫无疑问TLE

无奈又各种膜代码，发现PoPoQQQ的建虚树过程和DP放在一起搞…好神奇的样子

然后改呀改呀最终本地4S+ BZOJ 12S+

UPD: 发现了罪魁祸首，在建虚树过程中我傻逼地写了个$O(n)$级别的循环来赋初始值 = = 改完以后BZOJ 10S+…

首先把要建到虚树中的点按照DFS序排序

然后维护一个栈，从栈顶到栈底深度递减（栈底是根），保证从栈顶到栈底是一条需要建进虚树的路径，路径中只保留必要的点（询问的点与询问的点的LCA），这些点间的其他边和点都缩到一条边里

每次加一个点时把不在新加点到根的路径中的点依次弹出去，然后再把在路径中的点扔进来

每次弹栈的时候连边（其实如果把DP和建树放在一起的话就不用连边了）

比如说对于样例的10和6，步骤如下

  • 初始化 栈中有{1}
  • 将10加入栈中 栈中有{1,10}
  • 找到新加点6与栈顶10的LCA 5 发现深度小于栈顶 连边(1,10)并弹掉10 栈中有{1}
  • 将5加入栈中 栈中有{1,5}
  • 将6加入栈中 栈中有{1,5,6}
  • 依次连边(5,6),(1,5) 并依次弹 6,5,1

关于树形DP就不用提了吧…自己YY就好了


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
program bzoj_2286;
var dep,seq,lst,pos,s:array[0..250000]of longint;
    f:array[0..250000]of int64;
    fa,mn:array[0..500000,0..18]of longint;
    l:array[0..500000]of record ed,w,pre:longint; end;
    n,m,i,q,tot,a,b,c,len,logn:longint;
    energy:array[0..250000]of boolean;
 
procedure swap(var a,b:longint);
var p:longint;
begin
  p:=a;
  a:=b;
  b:=p;
end;
 
procedure link(a,b,w:longint);
begin
  inc(tot);
  l[tot].pre:=lst[a];
  lst[a]:=tot;
  l[tot].ed:=b;
  l[tot].w:=w;
end;
 
procedure dfs(t:longint);
var k:longint;
begin
  inc(len);
  pos[t]:=len;
  k:=lst[t];
  while k<>0 do
  begin
    if l[k].ed<>fa[t,0] then
    begin
      fa[l[k].ed,0]:=t;
      dep[l[k].ed]:=dep[t]+1;
      mn[l[k].ed,0]:=l[k].w;
      dfs(l[k].ed);
    end;
    k:=l[k].pre;
  end;
end;
 
procedure qsort(l,r:longint);
var i,j,mid:longint;
begin
  i:=l;
  j:=r;
  mid:=pos[seq[(l+r)>>1]];
  repeat
    while pos[seq[i]]<mid do inc(i);
    while pos[seq[j]]>mid do dec(j);
    if i<=j then
    begin
      swap(seq[i],seq[j]);
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then qsort(i,r);
  if l<j then qsort(l,j);
end;
 
function lca(a,b:longint):longint;
var l:longint;
begin
  if dep[a]<dep[b] then swap(a,b);
  for l:=logn downto 0 do
  if dep[fa[a,l]]>=dep[b] then a:=fa[a,l];
  if a=b then exit(a);
  for l:=logn downto 0 do if fa[a,l]<>fa[b,l] then
  begin
    a:=fa[a,l];
    b:=fa[b,l];
  end;
  exit(fa[a,0]);
end;
 
function getmin(a,b:longint):longint;
var l,ans:longint;
begin
  ans:=maxlongint;
  for l:=logn downto 0 do
  if dep[fa[a,l]]>=dep[b] then
  begin
    if mn[a,l]<ans then ans:=mn[a,l];
    a:=fa[a,l];
  end;
  exit(ans);
end;
 
procedure build;
var top,i,l,t:longint;
begin
  qsort(1,len);
  top:=1;
  s[1]:=1;
  f[1]:=0;
  energy[1]:=false;
  tot:=0;
  for i:=1 to len do
  begin
    l:=lca(seq[i],s[top]);
    while (top>1)and(dep[s[top-1]]>=dep[l]) do
    begin
      t:=getmin(s[top],s[top-1]);
      if (not energy[top])and(f[top]<t) then t:=f[top];
      inc(f[top-1],t);
      dec(top);
    end;
    if l<>s[top] then
    begin
      t:=getmin(s[top],l);
      if (not energy[top])and(f[top]<t) then t:=f[top];
      f[top]:=t;
      s[top]:=l;
      energy[top]:=false;
    end;
    inc(top);
    s[top]:=seq[i];
    energy[top]:=true;
  end;
  while top>1 do
  begin
    t:=getmin(s[top],s[top-1]);
    if (not energy[top])and(f[top]<t) then t:=f[top];
    inc(f[top-1],t);
    dec(top);
  end;
end;
 
begin
  readln(n);
  logn:=0;
  while 1<<logn<=n do inc(logn);
  tot:=0;
  for i:=1 to n-1 do
  begin
    readln(a,b,c);
    link(a,b,c);
    link(b,a,c);
  end;
  dep[1]:=1;
  fa[1,0]:=0;
  len:=0;
  dfs(1);
  for logn:=1 to logn do
  for i:=1 to n do
  begin
    fa[i,logn]:=fa[fa[i,logn-1],logn-1];
    if mn[i,logn-1]<mn[fa[i,logn-1],logn-1] then mn[i,logn]:=mn[i,logn-1] else mn[i,logn]:=mn[fa[i,logn-1],logn-1];
  end;
  readln(m);
  for q:=1 to m do
  begin
    read(len);
    for i:=1 to len do read(seq[i]);
    build;
    writeln(f[1]);
  end;
end.