咕咕咕的动态淀粉质

膜拜动态淀粉质。

首先动态淀粉质主要处理的是树上路径问题的修改与查询。对于某一个点 $rt$ 来说，其子树中的简单路径可以分成两种情况。（无根树）

• 经过 $rt$ 的，即可以理解为由 $rt$ 发散出去一条或两条路径。
• 不经过 $rt$，可以通过处理 $rt$ 的子树来进行处理。

所以我们现在只需要考虑第一种情况。

所以我们可以寻找当前处理的树的分治中心 $x$。
对于每一个分治中心，我们都可以将其所有子树视为几个连通块，然后删掉当前的节点 $rt$，递归分别处理，这样递归，构成一棵点分树。

那么很显然点分树每一层代表的节点个数都是 $\Theta(N)$ 级别的。

然后最深的递归层数显然是这棵树的深度。
那么很显然对于无根树我们把其根赋值为重心即可。

假设最深深度为 $d$，那么点分树建出来时间复杂度为 $\Theta(Nd)$。
那么使得 $d$ 最小就应该将分治中心设为每一个树上连通块的重心。
此时时间复杂度理论上最小，为 $\Theta(N \log N)$ 级别。

然后就这样递归乱搞就可以了。

淀粉质 AC 代码。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
const int M = 1e7 + 10;

int n, m, cnt, rt, totsiz, tot, head[N<<1];
int Maxi[N], siz[N], dist[N], Dis[N];
bool Exist[M], vis[N], hasret[N];
struct Edge { int to, nxt, val; } e[N<<1];
int query[N], MaxQue;

void addEdge(int u, int v, int w) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].val = w;
  head[u] = cnt; return ;
}

void calcsiz(int cur, int fa) {
  siz[cur] = 1, Maxi[cur] = 0;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa || vis[to]) continue;
    calcsiz(to, cur);
    Maxi[cur] = max(Maxi[cur], siz[to]);
    siz[cur] += siz[to];
  }
  Maxi[cur] = max(Maxi[cur], totsiz - siz[cur]);
  if (Maxi[cur] < Maxi[rt]) rt = cur;
  return ;
}

void calcdist(int cur, int fa) {
  Dis[++tot] = dist[cur];
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa || vis[to]) continue;
    dist[to] = dist[cur] + e[i].val;
    calcdist(to, cur);
  } return ;
}

queue <int> stat;
void dfs(int cur, int fa) {
  Exist[0] = vis[cur] = true; stat.push(0);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa || vis[to]) continue;
    dist[to] = e[i].val;
    calcdist(to, cur);
    for (int j=1; j<=m; ++j)
      for (int k=1; k<=tot; ++k)
        if (query[j]>=Dis[k])
          hasret[j] |= Exist[query[j]-Dis[k]];
    for (int j=1; j<=tot; ++j)
      if (Dis[j]<M)
        stat.push(Dis[j]), Exist[Dis[j]] = true;
    tot = 0;
  }
  while (!stat.empty())
    Exist[stat.front()] = false, stat.pop();
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa || vis[to]) continue;
    totsiz = siz[to], rt = 0;
    Maxi[0] = INT_MAX;
    calcsiz(to, cur), calcsiz(rt, -1);
    dfs(rt, cur);
  } return ;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

int main() {
  read(n), read(m);
  for (int i=1; i<n; ++i) {
    int u, v, w; read(u), read(v), read(w);
    addEdge(u, v, w), addEdge(v, u, w);
  }
  for (int i=1; i<=m; ++i)
    read(query[i]), MaxQue = max(MaxQue, query[i]);
  Maxi[0] = INT_MAX, totsiz = n;
  calcsiz(1, -1); calcsiz(rt, -1); dfs(rt, -1);
  for (int i=1; i<=m; ++i)
    puts(hasret[i]? "AYE" : "NAY");
  return 0;
}