JZOJ5143:无心行挽

Description

“What’s left to do when we’ve lost all hope?”
“若内心万念俱灰，是否注定无心行挽？”
------来自网易云音乐<Golden Leaves-Passenger>
不必做好输掉一切的准备。
所以，无畏结局。
在尽头，已经不能再做什么，来挽回。
在尽头，所有的一切都走向简化，没有了重复，没有了错杂，只剩下一片废墟。
就是说，世界曾是一副错杂的无向图，而在尽头，它已成为一个没有环的无向连通图，也就是说已成为一棵树。
这棵树有n个节点，有n-1条边，每条边的长度都是1。
给出q组询问，每组询问会给出k个关键点，设f(u)表示所有关键点中离点u最近的关键点离u的距离，求出最大的f(u)。

Input

第一行两个正整数n和q表示树的节点个数以及询问个数
接下来n-1行每行三个数u,v描述一条边，表示u和v之间有一条长度为1的无向边
接下来q组询问，每组询问第一行一个正整数k表示这组询问中关键点的个数，第二行k个正整数，表示这组询问的k个关键点。

Output

共q行，第i行对于第i组询问给出答案，详情见题目描述。

Sample Input

7 5

5 4

6 5

7 3

7 4

1 5

2 4

6 5 7 2

1 5 4 3 7

2 3

Sample Output

HINT

令S表示所有询问里k的和

对于20%的数据，1<=n,q,S<=3000

对于另外30%的数据，每组询问的k<=5

对于另外10%的数据，给出的树是一条链

对于另外20%的数据，1<=q<=10

对于100%的数据，1<=n,q,S<=100000

题解：

我们可以把树中的点根据距离其最近的关键点是什么来分类，即求出每个关键点“掌控”了哪些点。

建出虚树后，先从下往上做一次树形DP，求出虚树中每一个点往下距离最近的关键点；在从上往下做一次DFS，求出虚树中的每个点是被哪个关键点“掌控”（即比较上下的关键点哪个更近）。

对虚树中每一条边进行求解，根据距离两端的关键点的距离将一条边分为上下两份。

对于上方那份，用线段树求出其对应DPS序上最深的点，更新答案；对于下方那份，用倍增处理链上以及链上向外的子树中距离关键点最远的点，更新答案。

代码：

 uses math;

 const

   maxn=;

   inf=;

 var

   w:array[..*maxn,..]of longint;

   bel,dep,x,y,ans,t,size,key,cle,mxd,wz,ff:array[..maxn]of longint;

   tt:array[..maxn,-..]of longint;

   pos,mx:array[..maxn,..]of longint;

   st,bz:array[..maxn,..]of longint;

   i,j,k,tot,tt2:longint;

   n,m,len,a,b,top,cnt,anss:longint;

 procedure init(a,b:longint);

 begin

   w[len,]:=b; w[len,]:=;

   if w[a,]= then w[a,]:=len else w[w[a,],]:=len;

   w[a,]:=len; inc(len);

 end;

 procedure sort(l,r:longint);

 var i,j,a,b:longint;

 begin

   i:=l; j:=r; a:=pos[x[(l+r)div ],];

   repeat

     while pos[x[i],]<a do inc(i);

     while a<pos[x[j],] do dec(j);

     if not(i>j) then

     begin

       b:=x[i]; x[i]:=x[j]; x[j]:=b;

       inc(i); dec(j);

     end;

   until i>j;

   if l<j then sort(l,j);

   if i<r then sort(i,r);

 end;

 procedure dfs(a,fa:longint);

 var tt:longint;

 begin

   mx[a,]:=; mx[a,]:=; mxd[a]:=dep[a];

   tt:=w[a,]; inc(len); pos[a,]:=len; wz[len]:=a; size[a]:=;

   while tt<> do

   begin

     if w[tt,]<>fa then

     begin

       dep[w[tt,]]:=dep[a]+;

       st[w[tt,],]:=a; dfs(w[tt,],a);

       inc(size[a],size[w[tt,]]);

       if(mx[a,]=)or(mxd[w[tt,]]>mxd[mx[a,]])then

       begin mx[a,]:=mx[a,]; mx[a,]:=w[tt,]; mxd[a]:=mxd[w[tt,]]; end

       else if(mx[a,]=)or(mxd[w[tt,]]>mxd[mx[a,]])then mx[a,]:=w[tt,];

     end;

     tt:=w[tt,];

   end;

   pos[a,]:=len;

 end;

 procedure dfss(a,fa:longint);

 var tt:longint;

 begin

   if fa= then bz[a,]:= else

   begin

     if mx[fa,]=a then tt:=mx[fa,] else tt:=mx[fa,];

     if tt= then bz[a,]:= else bz[a,]:=+mxd[tt]-dep[fa];

   end;

   tt:=w[a,];

   while tt<> do

   begin

     if w[tt,]<>fa then dfss(w[tt,],a);

     tt:=w[tt,];

   end;

 end;

 function lca(a,b:longint):longint;

 var i:longint;

 begin

   if dep[a]<dep[b] then begin i:=a; a:=b; b:=i; end;

   for i:= downto  do

   if dep[st[a,i]]>=dep[b] then a:=st[a,i];

   if a=b then exit(a);

   for i:= downto  do

   if st[a,i]<>st[b,i] then begin a:=st[a,i]; b:=st[b,i]; end;

   exit(st[a,]);

 end;

 function get(fa,a:longint):Longint;

 var i:longint;

 begin

   for i:= downto  do

   if dep[st[a,i]]>dep[fa] then a:=st[a,i];

   exit(a);

 end;

 function dis(a,b:longint):longint;

 begin exit(dep[a]+dep[b]-*dep[lca(a,b)]); end;

 procedure dfs1(a:longint);

 var tt:longint;

 begin

   tt:=w[a,];

   if key[a]= then bel[a]:=a else bel[a]:=inf;

   while (tt<>) do

   begin

     dfs1(w[tt,]);

     if(bel[w[tt,]]<>inf)and((bel[a]=inf)

     or(dis(bel[w[tt,]],a)<dis(bel[a],a))

     or((dis(bel[w[tt,]],a)=dis(bel[a],a))and(bel[w[tt,]]<bel[a])))

     then bel[a]:=bel[w[tt,]];

     tt:=w[tt,];

   end;

 end;

 procedure dfs2(a,fa:longint);

 var tt:longint;

 begin

   ff[a]:=;

   if(a<>)and((dis(bel[fa],a)<dis(a,bel[a]))

   or((dis(bel[fa],a)=dis(a,bel[a]))and(bel[fa]<bel[a])))

   then begin bel[a]:=bel[fa]; ff[a]:=; end;

   tt:=w[a,];

   while tt<> do

   begin dfs2(w[tt,],a); tt:=w[tt,]; end;

 end;

 function work(a,x:longint):longint;

 var i,j,y:longint;

 begin

   if x= then exit();

   j:=; y:=;

   for i:= downto  do

   begin

     if j+(<<i)<=x then

     begin y:=max(y,j+bz[a,i]); a:=st[a,i]; j:=j+(<<i); end;

   end;

   exit(y);

 end;

 procedure build(l,r,fa:longint);

 var mid,x:longint;

 begin

   inc(tot); x:=tot; tt[x,]:=l; tt[x,]:=r;

   if tt[x,]=tt[fa,] then tt[fa,-]:=x else tt[fa,-]:=x;

   if l=r then begin tt[x,]:=dep[wz[l]]; exit; end;

   mid:=(l+r)>>;

   build(l,mid,x); build(mid+,r,x);

   tt[x,]:=max(tt[tt[x,-],],tt[tt[x,-],]);

 end;

 function find(x,l,r:longint):longint;

 var ll,rr,mid:longint;

 begin

   if l>r then exit();

   ll:=tt[x,]; rr:=tt[x,];

   if(ll=l)and(rr=r)then exit(tt[x,]);

   mid:=(ll+rr)>>;

   if r<=mid then exit(find(tt[x,-],l,r));

   if l>mid then exit(find(tt[x,-],l,r));

   exit(max(find(tt[x,-],l,mid),find(tt[x,-],mid+,r)));

 end;

 procedure solve(a,fa:longint);

 var tt,sum,aa,i,x,md,dis1,dis2,z:longint;

 begin

   if fa= then

   begin

     md:=work(a,dep[a]-dep[]);

     ans[bel[a]]:=max(ans[bel[a]],md+dis(a,bel[a]));

   end else

   begin

     tt:=get(fa,a); aa:=a;

     if bel[a]=bel[fa] then

     begin

       if ff[a]= then

       begin

         md:=find(,pos[tt,],pos[a,]-);

         md:=max(md,find(,pos[a,]+,pos[tt,]));

         ans[bel[a]]:=max(ans[bel[a]],md-dep[fa]+dis(fa,bel[a]));

       end else

       begin

         md:=work(a,dep[a]-dep[tt]);

         ans[bel[a]]:=max(ans[bel[a]],md+dis(a,bel[a]));

       end;

     end else

     begin

       dis1:=dis(fa,bel[fa]); dis2:=dis(a,bel[a]);

       for i:= downto  do

       begin

         if dep[st[aa,i]]<dep[tt] then continue;

         if(dep[a]-dep[st[aa,i]]+dis2<dep[st[aa,i]]-dep[fa]+dis1)

         or((dep[a]-dep[st[aa,i]]+dis2=dep[st[aa,i]]-dep[fa]+dis1)

         and(bel[a]<bel[fa]))then aa:=st[aa,i];

       end;

       md:=work(a,dep[a]-dep[aa]);

       ans[bel[a]]:=max(ans[bel[a]],dis(a,bel[a])+md);

       md:=find(,pos[tt,],pos[aa,]-);

       md:=max(md,find(,pos[aa,]+,pos[tt,]));

       ans[bel[fa]]:=max(ans[bel[fa]],md-dep[tt]+dis(tt,bel[fa]));

     end;

   end;

   md:=dep[a]; tt:=w[a,]; x:=pos[a,]-;

   while tt<> do

   begin

     z:=get(a,w[tt,]);

     md:=max(md,find(,x+,pos[z,]-));

     x:=pos[z,]; solve(w[tt,],a); tt:=w[tt,];

   end;

   md:=max(md,find(,x+,pos[a,]));

   ans[bel[a]]:=max(ans[bel[a]],md-dep[a]+dis(a,bel[a]));

 end;

 begin

   assign(input,'do.in'); reset(input);

   assign(output,'do.out'); rewrite(output);

   readln(n,m); len:=n+;

   for i:= to n- do

   begin readln(a,b); init(a,b); init(b,a); end;

   init(,); init(,); dep[]:=; len:=; dfs(,); dfss(,);

   for j:= to  do for i:= to n do

   st[i,j]:=st[st[i,j-],j-];

   for j:= to  do for i:= to n do

   if st[i,j-]> then bz[i,j]:=max(bz[i,j-],(<<(j-))+bz[st[i,j-],j-]);

   build(,n+,);

   fillchar(key,sizeof(key),);

   fillchar(bel,sizeof(bel),);

   fillchar(ans,sizeof(ans),);

   fillchar(w,sizeof(w),);

   for i:= to m do

   begin

     readln(cnt);

     for j:= to cnt do

     begin read(x[j]); y[j]:=x[j]; cle[j]:=x[j]; key[x[j]]:=; end;

     sort(,cnt); top:=; t[top]:=; len:=n+; cle[]:=cnt+; cle[cnt+]:=;

     for j:= to cnt do

     begin

       tt2:=lca(x[j],t[top]);

       while dep[tt2]<dep[t[top]] do

       begin

         if dep[t[top-]]<=dep[tt2] then

         begin

           init(tt2,t[top]); dec(top);

           if t[top]<>tt2 then

           begin inc(top); t[top]:=tt2; inc(cle[]); cle[cle[]]:=tt2; end;

           break;

         end;

         init(t[top-],t[top]); dec(top);

       end;

       inc(top); t[top]:=x[j];

     end;

     while top> do

     begin init(t[top-],t[top]); dec(top); end;

     dfs1(); dfs2(,); solve(w[w[,],],);

     anss:=;

     for j:= to cnt do anss:=max(anss,ans[y[j]]); writeln(anss);

     for j:= to cle[] do

     begin

       w[cle[j],]:=; key[cle[j]]:=;

       bel[cle[j]]:=inf; ans[cle[j]]:=;

     end;

   end;

   close(input); close(output);

 end.

巴特西