bzoj4042-蒲公英云

bzoj4042

比较好的树形dp，涉及到树上路径的题目，我们往往考虑对路径分类

当我们考虑以x为根的子树，有这样几类路径

起点终点都在子树内
一个点延伸到子树外

对于要选择另一个点在子树外的路径，要建立在不破坏儿子子树内的路径基础上

因为破坏会破坏多条，而只能多选择一条，不合适

因此我们考虑树dp，设f[x]为路径起点终点在子树内能选择的最多路径数目，d[x]表示还没用过的另一个点在x子树外的路径的集合

我们知道，对于x的每个孩子d，d[y]中最多只会有1条路径被选中，因此我们可以用状压dp解决

1 type node=record
  2        po,next:longint;
  3      end;
  4 
  5 var a:array[0..1200,0..1200] of longint;
  6     w:array[0..1010,0..1010] of boolean;
  7     e:array[0..2400] of node;
  8     g,f,q,b,s,p:array[0..1200] of longint;
  9     len,i,tt,n,m,x,y:longint;
 10 
 11 function max(a,b:longint):longint;
 12   begin
 13     if a>b then exit(a) else exit(b);
 14   end;
 15 
 16 procedure add(x,y:longint);
 17   begin
 18     inc(len);
 19     e[len].po:=y;
 20     e[len].next:=p[x];
 21     p[x]:=len;
 22   end;
 23 
 24 function check(x,y:longint):boolean;
 25   var i,j:longint;
 26   begin
 27     for i:=1 to s[x] do
 28       for j:=1 to s[y] do
 29         if w[a[x,i],a[y,j]] then exit(true);
 30     exit(false);
 31   end;
 32 
 33 procedure dfs(x,fa:longint);
 34   var st,mx,i,y,t,j,k:longint;
 35   begin
 36     f[x]:=0;
 37     s[x]:=1;
 38     a[x,s[x]]:=x;
 39     i:=p[x];
 40     while i<>0 do
 41     begin
 42       y:=e[i].po;
 43       if y<>fa then
 44         dfs(y,x);
 45       i:=e[i].next;
 46     end;
 47     i:=p[x];
 48     t:=0;
 49     while i<>0 do
 50     begin
 51       y:=e[i].po;
 52       if y<>fa then
 53       begin
 54         f[x]:=f[x]+f[y];
 55         if check(x,y) then inc(f[x])
 56         else begin
 57           inc(t);
 58           q[t]:=y;
 59         end;
 60       end;
 61       i:=e[i].next;
 62     end;
 63     k:=0;
 64     for i:=1 to t-1 do
 65       for j:=i+1 to t do
 66         if check(q[i],q[j]) then
 67         begin
 68           inc(k);
 69           b[k]:=(1 shl (i-1)) or (1 shl (j-1));
 70         end;
 71     st:=0;
 72     mx:=0;
 73     for i:=0 to 1 shl t-1 do
 74     begin
 75       g[i]:=0;
 76       for j:=1 to k do
 77         if b[j] and i=b[j] then
 78           g[i]:=max(g[i],g[i xor b[j]]+1);
 79       if g[i]>mx then
 80       begin
 81         mx:=g[i];
 82         st:=0;
 83       end;
 84       if g[i]=mx then st:=st or ((1 shl t-1) xor i);
 85     end;
 86     f[x]:=f[x]+mx;
 87     for i:=1 to t do
 88       if (1 shl (i-1)) and st>0 then
 89       begin
 90         y:=q[i];
 91         for j:=1 to s[y] do
 92         begin
 93           inc(s[x]);
 94           a[x,s[x]]:=a[y,j];
 95         end;
 96       end;
 97   end;
 98 
 99 begin
100   readln(tt);
101   while tt>0 do
102   begin
103     dec(tt);
104     len:=0;
105     fillchar(p,sizeof(p),0);
106     readln(n);
107     for i:=1 to n-1 do
108     begin
109       readln(x,y);
110       add(x,y);
111       add(y,x);
112     end;
113     readln(m);
114     fillchar(w,sizeof(w),false);
115     for i:=1 to m do
116     begin
117       readln(x,y);
118       w[x,y]:=true;
119       w[y,x]:=true;
120     end;
121     dfs(1,0);
122     writeln(f[1]);
123   end;
124 end.