题解 P5024 【保卫王国】

fysbb · 2018-11-22 00:09:32 · 题解

作为NOIP2018的Day2T3，这题也是非常恶心了，思维难度大，程序复杂。很多大佬说这题是动态DP模板，但我这个蒟蒻完全不了解动态DP，经过思考，我终于了解到如何用LCA倍增思想解决这道题，现在就让我们一起来进行分析。

1.对于前11组数据：

先思考简单的暴力做法，题目说明每个点可以选或不选，所以我们用：

$dp[i,0]$表示以i为根的子树，在i节点不选时的最小费用同时，还要求相邻的两个节点至少有一个要选，所以**如果 $i$ 不选，则 $i$ 的所有叶节点必须都选，如果 $i$ 选择，则叶节点选和不选都可以**。以此得到状态转移（ $j$ 为 $i$ 的叶节点，$a[i]$ 为 $i$ 节点的权值）： $dp[i,1]=\sum min(dp[j,1],dp[j,0])+a[i]

dp[i,0]=\sum dp[j,1]

之后对于每个询问，都进行一次DP，最后输出min(dp[1,1],dp[1,0])

对于处理一个节点是否必须要选/不选，只需将其权值改为0/maxint即可。

时间复杂度O(n \cdot m)，可以通过前11个点。

program project1;
var
   dp:array[0..100005,0..1]of int64;
   a,r:array[0..100005]of longint;
   l,v:array[0..200005]of longint;
   n,m:longint;

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;

procedure re;
var i,t,x,y:longint;
    s:string;
begin
  readln(s);
  for i:=1 to n do read(a[i]);
  for i:=1 to n-1 do begin
    t:=i*2;
    read(x,y);
    l[t]:=r[x];
    r[x]:=t;
    v[t]:=y;
    l[t-1]:=r[y];
    r[y]:=t-1;
    v[t-1]:=x;
  end;
end;

procedure sc(f,fa:longint);
var i:longint;
begin
  i:=r[f];
  while i<>0 do begin
    if v[i]<>fa then begin
      sc(v[i],f);
      dp[f,1]:=dp[f,1]+min(dp[v[i],0],dp[v[i],1]);
      dp[f,0]:=dp[f,0]+dp[v[i],1];
    end;
    i:=l[i];
  end;
  dp[f,1]:=dp[f,1]+a[f];
end;

procedure main;
var i,j,x,y,tx,ty,ans,p,q:longint;
begin
  for i:=1 to m do begin
    read(x,tx,y,ty);
    ans:=0;
    p:=a[x];
    q:=a[y];
    fillchar(dp,sizeof(dp),0);
    if tx=1 then begin
      ans:=ans+a[x];
      a[x]:=0;
    end else a[x]:=1000000000;
    if ty=1 then begin
      ans:=ans+a[y];
      a[y]:=0;
    end else a[y]:=1000000000;
    sc(1,0);
    ans:=min(ans+dp[1,1],ans+dp[1,0]);
    if ans>=1000000000 then writeln('-1')
      else writeln(ans); 
    a[x]:=p;
    a[y]:=q;
  end;
end;

begin
  read(n,m);
  fillchar(a,sizeof(a),0);
  re;
  main;
end.

2.对于B类型数据：

在之间的基础上进行分析，我们发现对于每一次询问，除了被询问的两个点之间的链上，各节点的答案会发生改变，其余节点的答案是不变的。

比如下图（询问 O 和 M ）：

则只有 O K D M 四个节点的答案需要更新。

由此，我们可以有一个玄学的优化，即再用一个数组ndp保存：

$ndp[i,0]$整棵树除去以 $i$ 为根的子树，$i$ 不选时的最小费用状态转移为（ $j$ 为 $i$ 的叶节点）： $ndp[j,1]:=min(ndp[i,0]+dp[i,0]-dp[j,1],ndp[i,1]+dp[i,1]-min(dp[j,0],dp[j,1]))

ndp[j,0]:=ndp[i,1]+dp[i,1]-min(dp[j,0],dp[j,1])

之后对于每次询问，只需对两个节点之间的链进行维护，一直维护到两个节点的最近公共祖先处。

设它们的最近公共祖先为 t ,ans[1]为 t 选择时的最小费用, ans[0] 为 t 不选时的最小费用，最后输出min(ans[0]+ndp[t,0],ans[1]+ndp[t,1])

假设链的平均长度为 H ,时间复杂度接近O(m \cdot H),可以通过所有的B类型数据，如果数据不极端，也许能通过更多测试点。

这棵树退化的越接近一条链，这个玄学优化的性能越差，最坏时间复杂度仍接近O(n \cdot m)

program project1;
var
   dp,ndp,dp2:array[0..100005,0..1]of int64;
   a,r,father,deep:array[0..100005]of longint;
   l,v:array[0..200005]of longint;
   n,m:longint;

function min(a,b:int64):int64;
begin
  if a<b then exit(a) else exit(b);
end;

procedure re;
var i,t,x,y:longint;
    s:string;
begin
  readln(s);
  for i:=1 to n do read(a[i]);
  for i:=1 to n-1 do begin
    t:=i*2;
    read(x,y);
    l[t]:=r[x];
    r[x]:=t;
    v[t]:=y;
    l[t-1]:=r[y];
    r[y]:=t-1;
    v[t-1]:=x;
  end;
end;

procedure sc(f,fa:longint);
var i:longint;
begin
  father[f]:=fa;
  deep[f]:=deep[fa]+1;
  i:=r[f];
  while i<>0 do begin
    if v[i]<>fa then begin
      sc(v[i],f);
      dp[f,1]:=dp[f,1]+min(dp[v[i],0],dp[v[i],1]);
      dp[f,0]:=dp[f,0]+dp[v[i],1];
    end;
    i:=l[i];
  end;
  dp[f,1]:=dp[f,1]+a[f];
end;

procedure sc2(f,fa:longint);
var i:longint;
begin
  i:=r[f];
  while i<>0 do begin
    if v[i]<>fa then begin
      ndp[v[i],1]:=min(ndp[f,0]+dp[f,0]-dp[v[i],1],ndp[f,1]+dp[f,1]-min(dp[v[i],0],dp[v[i],1]));
      ndp[v[i],0]:=ndp[f,1]+dp[f,1]-min(dp[v[i],0],dp[v[i],1]);
      sc2(v[i],f);
    end;
    i:=l[i];
  end;
end;

function ans(x,y:longint):int64;
var i,t:longint;
begin
  if deep[x]<deep[y] then begin
    t:=x;
    x:=y;
    y:=t;
  end;
  while (deep[x]>deep[y]) and (father[x]<>y) do begin
    t:=father[x];
    dp2[t,1]:=dp[t,1]-min(dp[x,0],dp[x,1])+min(dp2[x,0],dp2[x,1]);
    dp2[t,0]:=dp[t,0]-dp[x,1]+dp2[x,1];
    x:=t;
  end;
  if father[x]=y then begin
    t:=y;
    dp2[t,1]:=dp2[t,1]-min(dp[x,0],dp[x,1])+min(dp2[x,0],dp2[x,1]);
    dp2[t,0]:=dp2[t,0]-dp[x,1]+dp2[x,1];
    x:=t;
  end;
  while father[x]<>father[y] do begin
    t:=father[x];
    dp2[t,1]:=dp[t,1]-min(dp[x,0],dp[x,1])+min(dp2[x,0],dp2[x,1]);
    dp2[t,0]:=dp[t,0]-dp[x,1]+dp2[x,1];
    x:=t;
    t:=father[y];
    dp2[t,1]:=dp[t,1]-min(dp[y,0],dp[y,1])+min(dp2[y,0],dp2[y,1]);
    dp2[t,0]:=dp[t,0]-dp[y,1]+dp2[y,1];
    y:=t;
  end;
  if x<>y then begin
    t:=father[x];
    dp2[t,1]:=dp[t,1]-min(dp[x,0],dp[x,1])+min(dp2[x,0],dp2[x,1])-min(dp[y,0],dp[y,1])+min(dp2[y,0],dp2[y,1]);
    dp2[t,0]:=dp[t,0]-dp[x,1]-dp[y,1]+dp2[x,1]+dp2[y,1];
    x:=t;
  end;
  exit(min(dp2[t,0]+ndp[t,0],dp2[t,1]+ndp[t,1]));
end;

procedure main;
var i,x,y,tx,ty:longint;
    sum:int64;
begin
  for i:=1 to m do begin
    read(x,tx,y,ty);
    if tx=1 then begin
      dp2[x,1]:=dp[x,1];
      dp2[x,0]:=1000000000000;
    end else begin
      dp2[x,1]:=1000000000000;
      dp2[x,0]:=dp[x,0];
    end;
    if ty=1 then begin
      dp2[y,1]:=dp[y,1];
      dp2[y,0]:=1000000000000;
    end else begin
      dp2[y,1]:=1000000000000;
      dp2[y,0]:=dp[y,0];
    end;
    sum:=ans(x,y);
    if sum<1000000000000 then writeln(sum)
      else writeln('-1');
  end;
end;

begin
  read(n,m);
  fillchar(a,sizeof(a),0);
  fillchar(father,sizeof(father),0);
  fillchar(dp,sizeof(dp),0);
  fillchar(deep,sizeof(deep),0);
  fillchar(ndp,sizeof(ndp),0);
  re;
  sc(1,0);
  sc2(1,0);
  main;
end.

3.对于全部的数据：

以上的玄学优化虽然不能AC此题，但却提供了一个可供发展的思路。可以看出，我们在对这条链进行处理时，相当于一直向上遍历寻找这两个点的最近公共祖先，并将DP值更新。所以我们可以对更新的方式进行优化，不再是一个点一个点的向上遍历，而是采用类似LCA倍增的方法，加快处理速度。

我们用 lca 数组存储：

lca[i,t,p,q]$为 $i$ 结点向上倍增到其 $2^{t}$ 的节点，其中 $i$ 节点 $p$ 情况 $2^{t}$ 节点 $q$ 情况时的最小费用加和（不包括 $i$ 子树的费用）。$p =0,1$ ; $q=0,1

状态转移为：

lca[i,t,p,q]=min(lca[i,t-1,p,0]+lca[father[i,t-1],t-1,0,q],lca[i,t-1,p,1]+lca[father[i,t-1],t-1,1,q])

依靠此状态转移方程对lca进行预处理，之后对于每一次询问，即可凭借lca数组通过倍增方式进行处理：

设当前节点为 i ，当前节点答案为 ans , 2^{t} 节点答案 sum ,则转移方程为：

sum[q]:=min(sum[q],lca[i,t,p,q]+ans[p])

处理完之后向上倍增：

i=father[i,t]

ans=sum

倍增过程就和求LCA的方式基本一样了。

设链的平均长度为 H ，该方法需要预处理 lca 数组，时间复杂度接近 O(n \cdot \log H) ，然后对于每次询问处理的时间复杂度接近 O(\log H)，所以总的时间复杂度接近 O((n+m) \cdot \log H) ,即使树完全退化成一条链，最坏的时间复杂度也为 O((n+m) \cdot \log n) ，可以通过所有数据。

program project1;
var
   dp,ndp:array[0..100005,0..1]of int64;
   a,r,deep:array[0..100005]of longint;
   father:array[0..100005,0..25]of longint;
   lca:array[0..100005,0..25,0..1,0..1]of int64;
   l,v:array[0..200005]of longint;
   n,m:longint;

function min(a,b:int64):int64;
begin
  if a<b then exit(a) else exit(b);
end;

procedure re;
var i,t,x,y:longint;
    s:string;
begin
  readln(s);
  for i:=1 to n do read(a[i]);
  for i:=1 to n-1 do begin
    t:=i*2;
    read(x,y);
    l[t]:=r[x];
    r[x]:=t;
    v[t]:=y;
    l[t-1]:=r[y];
    r[y]:=t-1;
    v[t-1]:=x;
  end;
end;

procedure sc(f,fa:longint);
var i:longint;
begin
  father[f,0]:=fa;
  deep[f]:=deep[fa]+1;
  i:=r[f];
  while i<>0 do begin
    if v[i]<>fa then begin
      sc(v[i],f);
      dp[f,1]:=dp[f,1]+min(dp[v[i],0],dp[v[i],1]);
      dp[f,0]:=dp[f,0]+dp[v[i],1];
    end;
    i:=l[i];
  end;
  dp[f,1]:=dp[f,1]+a[f];
end;

procedure sc2(f,fa:longint);
var i:longint;
begin
  i:=r[f];
  while i<>0 do begin
    if v[i]<>fa then begin
      ndp[v[i],1]:=min(ndp[f,0]+dp[f,0]-dp[v[i],1],ndp[f,1]+dp[f,1]-min(dp[v[i],0],dp[v[i],1]));
      ndp[v[i],0]:=ndp[f,1]+dp[f,1]-min(dp[v[i],0],dp[v[i],1]);
      sc2(v[i],f);
    end;
    i:=l[i];
  end;
end;

procedure lca_up;     //预处理lca数组
var i,t,p,q:longint;
begin
  for i:=1 to n do begin
    lca[i,0,0,0]:=1000000000000;
    lca[i,0,0,1]:=dp[father[i,0],1]-min(dp[i,0],dp[i,1]);
    lca[i,0,1,0]:=dp[father[i,0],0]-dp[i,1];
    lca[i,0,1,1]:=dp[father[i,0],1]-min(dp[i,0],dp[i,1]);
  end;
  for t:=1 to 20 do
    for i:=1 to n do begin
      father[i,t]:=father[father[i,t-1],t-1];
       for p:=0 to 1 do
         for q:=0 to 1 do begin
           lca[i,t,p,q]:=1000000000000;
           lca[i,t,p,q]:=min(lca[i,t,p,q],lca[i,t-1,p,0]+lca[father[i,t-1],t-1,0,q]);
           lca[i,t,p,q]:=min(lca[i,t,p,q],lca[i,t-1,p,1]+lca[father[i,t-1],t-1,1,q]);
         end;
    end;
end;

function ans(x,tx,y,ty:longint):int64;
var i,t,p,q:longint;
    sumx,sumy,ansx,ansy:array[0..1]of int64;
begin
  if deep[x]<deep[y] then begin
    t:=x;
    x:=y;
    y:=t;
    t:=tx;
    tx:=ty;
    ty:=t;
  end;
  ansx[1]:=1000000000000;
  ansx[0]:=1000000000000;
  ansy[1]:=1000000000000;
  ansy[0]:=1000000000000;
  ansx[tx]:=dp[x,tx];
  ansy[ty]:=dp[y,ty];
  for t:=20 downto 0 do  begin
    if deep[x]-(1 shl t)>=deep[y] then begin
      sumx[0]:=1000000000000;
      sumx[1]:=1000000000000;
      for p:=0 to 1 do
        for q:=0 to 1 do
          sumx[q]:=min(sumx[q],lca[x,t,p,q]+ansx[p]);
      ansx[1]:=sumx[1];
      ansx[0]:=sumx[0];
      x:=father[x,t];
    end;
  end;
  if x=y then exit(ansx[ty]+ndp[x,ty]);
  for t:=20 downto 0 do
    if father[x,t]<>father[y,t] then begin
      sumx[0]:=1000000000000;
      sumx[1]:=1000000000000;
      sumy[0]:=1000000000000;
      sumy[1]:=1000000000000;
      for p:=0 to 1 do
        for q:=0 to 1 do begin
          sumx[q]:=min(sumx[q],lca[x,t,p,q]+ansx[p]);
          sumy[q]:=min(sumy[q],lca[y,t,p,q]+ansy[p]);
        end;
      ansx[0]:=sumx[0];
      ansx[1]:=sumx[1];
      ansy[0]:=sumy[0];
      ansy[1]:=sumy[1];
      x:=father[x,t];
      y:=father[y,t];
    end;
  p:=father[x,0];
  exit(min(dp[p,0]-dp[x,1]-dp[y,1]+ansx[1]+ansy[1]+ndp[p,0],dp[p,1]-min(dp[x,0],dp[x,1])-min(dp[y,0],dp[y,1])+min(ansx[0],ansx[1])+min(ansy[0],ansy[1])+ndp[p,1]));
end;

procedure main;
var i,x,y,tx,ty:longint;
    sum:int64;
begin
  for i:=1 to m do begin
    read(x,tx,y,ty);
    sum:=ans(x,tx,y,ty);
    if sum<1000000000000 then writeln(sum)
      else writeln('-1');
  end;
end;

begin
  read(n,m);
  fillchar(a,sizeof(a),0);
  fillchar(father,sizeof(father),0);
  fillchar(dp,sizeof(dp),0);
  fillchar(deep,sizeof(deep),0);
  fillchar(ndp,sizeof(ndp),0);
  fillchar(lca,sizeof(lca),0);
  re;
  sc(1,0);
  sc2(1,0);
  lca_up;
  main;
end.