Write in front

Coo

introduce

P3806 [template] point divide and conquer 1

Given a tree with \ (n \) nodes, the edge has edge weight. Given \ (m \) queries, each time ask whether the point pair with distance \ (k \) on the tree exists.
\(1\le n\le 10^4 \), \ (1\le m\le 100 \), \ (1\le k\le 10^7 \), \ (1\le \) edge weight \ (\ le 10^4 \).
200ms，512MB.

For a single query, the complexity of enumerating point pairs and statistical information is \ (O(n^2) \) level. The point divide and conquer algorithm transforms the path problem into the problem of the chain to the root by properly selecting the root node. The complexity of statistics is reduced by memorizing the chain information, and a single query can be completed within the time complexity of \ (O(n\log n) \).

analysis

First, choose a root node at will. At this time, the paths on the tree are divided into two types: those that pass through the root node and those that do not.
First, for paths passing through the root node, they can be spliced by up to two chains with the root node as the endpoint. Considering that dfs preprocesses the weight sum of the chain with the root node as the endpoint, the problem becomes whether there are at most two weights in them, and the sum is \ (k \), just open a bucket.

The second step is to recursively process the path that is not the root node by taking other nodes in its subtree as the new root node.
After the first step is completed, all paths passing through the old root have been counted. When enumerating the chains after updating the root node, you can not count the chains passing through the old root. It can be found that the subtrees of the old root are independent of each other. A new root node needs to be selected in each subtree. Each subtree can be regarded as a smaller subproblem.

The following figure shows an example of the above process:

Consider complexity. On the full binary tree shown in the figure, select a new root node by dfs order as shown in the figure, and its time complexity is obviously \ (O(n\log n) \). However, this method of selecting new root nodes will obviously be stuck to the \ (O(n^2) \) level on the chain diagram.
More generally, let the \ (1 \) root selected in the above process form the \ (1 \) level root set, and the new roots selected by all the points in the \ (r \) level root set in the second step form the \ (r+1 \) level root set. It can be found that for "arbitrary level root sets", when they are counted as new roots in the first step, the number of all nodes traversed is \ (O(n) \) level. Then the total time complexity of the above algorithm is \ (O(nr_{max}) \).
Obviously, each time the root node is randomly selected in a random tree, the expected value of \ (r_{max} \) is \ (\ log n \), and the total complexity of the above algorithm is \ (O(n\log n) \).

On any tree, in order to minimize \ (r_{Max} \), it is obvious that the center of gravity of the subtree should be selected as the new root node each time. Its correctness is obvious. When taking the center of gravity as the root, the size of each subtree does not exceed \ (\ frac{n}{2} \), then the size of the subtree will change to \ (1 \) after selecting a new root at most \ (\ log n \), so as to ensure that \ (r_{max} \) is stable at the \ (\ log n \) level.

code

P3806 [template] point divide and conquer 1

Note that before re selecting the root node each time, you need to recalculate the subtree size and select a new root through the new subtree size.

//Knowledge points: divide and conquer
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define LL long long
const int kN = 1e4 + 10;
const int kM = 110;
const int kMaxDis = 1e7 + 10;
//=============================================================
int n, m, e_num, k[kM], head[kN], v[kN << 1], w[kN << 1], ne[kN << 1];
int root, sumsz, sz[kN], maxsz[kN], dis[kN];
bool ans[kM], vis[kN], exist[kMaxDis];
std::vector <int> tmp;
std::queue <int> tag;
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void Chkmin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
void Add(int u_, int v_, int w_) {
  v[++ e_num] = v_, w[e_num] = w_;
  ne[e_num] = head[u_], head[u_] = e_num;
}
void CalcSize(int u_, int fa_) {
  sz[u_] = 1, maxsz[u_] = 0;
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || vis[v_]) continue;
    CalcSize(v_, u_);
    Chkmax(maxsz[u_], sz[v_]);
    sz[u_] += sz[v_];
  }
  Chkmax(maxsz[u_], sumsz - sz[u_]);
  if (maxsz[u_] < maxsz[root]) root = u_;
}
void CalcDis(int u_, int fa_) {
  tmp.push_back(dis[u_]);
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i], w_ = w[i];
    if (v_ == fa_ || vis[v_]) continue;
    dis[v_] = dis[u_] + w_;
    CalcDis(v_, u_);
  }
}
void Dfs(int u_, int fa_) {
  exist[0] = true;
  tag.push(0);
  vis[u_] = true;
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i], w_ = w[i];
    if (v_ == fa_ || vis[v_]) continue;
    dis[v_] = w_;
    CalcDis(v_, u_);
    for (int j = 0, lim = tmp.size(); j < lim; ++ j) {
      for (int l = 1; l <= m; ++ l) {
        if (k[l] >= tmp[j]) ans[l] |= exist[k[l] - tmp[j]];
      }
    }
    for (int j = 0, lim = tmp.size(); j < lim; ++ j) {
      if (tmp[j] < kMaxDis) {
        tag.push(tmp[j]);
        exist[tmp[j]] = true;
      }
    }
    tmp.clear();
  }
  while (!tag.empty()) {
    exist[tag.front()] = false;
    tag.pop();
  }

  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || vis[v_]) continue;
    sumsz = sz[v_];
    root = 0, maxsz[root] = kN;
    CalcSize(v_, u_), CalcSize(root, 0), Dfs(root, 0);
  }
}
//=============================================================
int main() { 
  n = read(), m = read();
  for (int i = 1; i < n; ++ i) {
    int u_ = read(), v_ = read(), w_ = read();
    Add(u_, v_, w_), Add(v_, u_, w_);
  }
  for (int i = 1; i <= m; ++ i) k[i] = read();
  
  sumsz = n;
  root = 0, maxsz[root] = kN;
  CalcSize(1, 0), CalcSize(root, 0), Dfs(root, 0);
  for (int i = 1; i <= m; ++ i) printf("%s\n", ans[i] ? "AYE" : "NAY");
  return 0;
}