2019.2.18

长沙集训 $ Day 8 $

$ Day 6 $ 讲解了 $ CDQ $ 分治，今天有学到了一种树上分治方法——点分治。

---

点分治:

给出一棵树，询问树上有无距离为 $ k $ 的点对存在。

对于此类问题，最基础的方法是 $ DFS $ 树上的每一条链，寻找有无链长为 $ k $ ,但是这样的做法时间复杂度为 $ O(n^{2}) $ ,肯定会 $ TLE $ 。这时，我们便可使用点分治来解决问题。

实际上，如果选一个节点为根，树上的链可以分成两种，即经过树根和在子树中。

而这便是点分治的基础，我们选择一个根，进行一次 $ DFS $ ，处理完所有经过根的路径，之后我们将根删除。原有的树被分为多棵子树，在所有子树中进行同样的操作，直到所有节点都被删除。

但根节点的选择也是有技巧的，如上图中选择 $ R $ 为根和选择 $ K $ 为根，分治的次数是不同的，如何选取一个节点，使分治次数最少？事实上，这个点就是树的重心。

树的重心

性质：以删去重心后，形成所有子树中，最大的子树最小。

如上图中，树的重心为 $ R $ 。因为以 $ R $ 为根时，最大子树为 $ 4 $ ，其余各点为根时，没有任何一个点能使最大子树小于 $ 4 $ 。

我们可以利用性质来寻找树的重心，只需通过一次树形 $ DP $ ，找出每个点的最大子树即可。

procedure find(f,fa,sum_root:longint);  //sum_root为整棵树的大小，f为当前节点，fa为f的父节点
var i:longint;
begin
  i:=r[f];
  sum[f]:=0;          //sum[f]记录以f为根的子树的大小，max_next[f]记录删去f后形成的最大子树大小
  max_next[f]:=0;
  while i<>0 do begin
    if (v[i]<>fa) and (tf[v[i]]=false) then begin
      find(v[i],f,sum_root);
      inc(sum[f],sum[v[i]]);
      max_next[f]:=max(max_next[f],sum[v[i]]);
    end;
    i:=l[i];
  end;
  inc(sum[f]);
  max_next[f]:=max(max_next[f],sum_root-sum[f]);
  if (max_next[f]<max_next[find_root]) or (find_root=0) then find_root:=f;    //  find_root记录重心
end;

分治处理

找到重心后，我们便可以通过DFS查找答案，但此时要注意这种特殊情况。

像这样的两条链是不能将他们的长度加在一起的，但显然这种情况在记录答案时是不好处理的，所以我们可以跑两遍 $ DFS $ ，第一遍记录答案（不论正误），第二遍将错误的答案减掉。

procedure dfs(f,fa,len:longint);
var i:longint;
begin
  i:=r[f];
  inc(tot);
  dis[tot]:=len;
  while i<>0 do begin
    if (v[i]<>fa) and (tf[v[i]]=false) then dfs(v[i],f,len+w[i]);
    i:=l[i];
  end;
end;

function solve(q,k:longint;len:int64):int64;
var i,j:longint;
begin
  tot:=0;  
  dfs(q,0,len);
  if k=1 then begin
    for i:=1 to tot do
      for j:=i+1 to tot do
        inc(ans[dis[i]+dis[j]]);
  end
    else begin
      for i:=1 to tot do
        for j:=i+1 to tot do
          dec(ans[dis[i]+dis[j]]);
    end;
end;

procedure next(q:longint);
var i:longint;
begin
  tf[q]:=true;
  solve(q,1,0);             //注意这两次solve时参数的不同
  i:=r[q];  
  while i<>0 do begin
    if tf[v[i]]=false then begin
      solve(v[i],0,w[i]);  
      find_root:=0;
      find(v[i],q,sum[v[i]]); 
      next(find_root);
    end;
    i:=l[i];
  end;
end;

复杂度

根据树的重心的性质，我们可以确定分治次数不超过 $ \log n $ 次，由此可得出算法的时间复杂度：

1. 分治 $ O(\log n) $
2. 查找答案 $ O(n) $

总时间复杂度接近 $ O(n \log n) $

其实点分治的难点并不在分治，而是在计算答案的过程，某些题目中不能单纯使用暴力计算答案，还要和其他算法、数据结构相结合（如二分、树状数组），又或者计算答案的过程十分繁琐（如树上游戏），所以还是需要熟练运用多种算法才能顺利解决点分治问题。

程序

program project1;
var
   r,sum,max_next,dis:array[0..10005]of longint;
   tf:array[0..10005]of boolean;
   ans:array[0..10000005]of longint;
   l,v,w:array[0..20005]of longint;
   n,m,find_root,tot:longint;

function max(a,b:int64):int64;
begin
  if a>b then exit(a) else exit(b);
end;

procedure re;
var i,t,x,y,z:longint;
begin
  t:=0;
  for i:=1 to n-1 do begin
    read(x,y,z);
    inc(t);
    l[t]:=r[x];
    r[x]:=t;
    v[t]:=y;
    w[t]:=z;
    inc(t);
    l[t]:=r[y];
    r[y]:=t;
    v[t]:=x;
    w[t]:=z;
  end;
end;

procedure find(f,fa,sum_root:longint);
var i:longint;
begin
  i:=r[f];
  sum[f]:=0;
  max_next[f]:=0;
  while i<>0 do begin
    if (v[i]<>fa) and (tf[v[i]]=false) then begin
      find(v[i],f,sum_root);
      inc(sum[f],sum[v[i]]);
      max_next[f]:=max(max_next[f],sum[v[i]]);
    end;
    i:=l[i];
  end;
  inc(sum[f]);
  max_next[f]:=max(max_next[f],sum_root-sum[f]);
  if (max_next[f]<max_next[find_root]) or (find_root=0) then find_root:=f;
end;

procedure dfs(f,fa,len:longint);
var i:longint;
begin
  i:=r[f];
  inc(tot);
  dis[tot]:=len;
  while i<>0 do begin
    if (v[i]<>fa) and (tf[v[i]]=false) then dfs(v[i],f,len+w[i]);
    i:=l[i];
  end;
end;

function solve(q,k:longint;len:int64):int64;
var i,j:longint;
begin
  tot:=0;   
  dfs(q,0,len);
  if k=1 then begin
    for i:=1 to tot do
      for j:=i+1 to tot do
        inc(ans[dis[i]+dis[j]]);
  end
    else begin
      for i:=1 to tot do
        for j:=i+1 to tot do
          dec(ans[dis[i]+dis[j]]);
    end;
end;

procedure next(q:longint);
var i:longint;
begin
  tf[q]:=true;
  solve(q,1,0);
  i:=r[q];  
  while i<>0 do begin
    if tf[v[i]]=false then begin
      solve(v[i],0,w[i]);
      find_root:=0;
      find(v[i],q,sum[v[i]]); 
      next(find_root);
    end;
    i:=l[i];
  end;
end;

procedure main;
var i,x:longint;
begin
  for i:=1 to m do begin
    read(x);
    if ans[x]<>0 then writeln('AYE')
      else writeln('NAY');
  end;
end;

begin
  read(n,m);
  re;
  find_root:=0;
  find(1,0,n); 
  next(find_root);
  main;
end.