bzoj4042

ゝ一世哀愁。 2021-12-23 07:37 132阅读 0赞

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

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

1. 起点终点都在子树内

2. 一个点延伸到子树外

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

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

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

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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.

转载于:https://www.cnblogs.com/phile/p/4590630.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211223/3a09bb8f54d14773bd21631ffb096449.png