P3806 【模板】点分治1 （点分治求树上是否存在长为k的路径）

思路： 离线求，把询问的$1到m$存入pre数组里，设当前根节点为$rt$，当前子树$v_i$，求出$v_i$的每个子节点到$rt$的距离$dep[i]$，令$is$数组存从$v_0$到$v_{i-1}$里是否存在某个节点到$rt$的距离为$pre[i]$，若有，则表示路径长为$pre[i]$存在。

#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 2e4 + 10; int n, sn, m, h[N], cnt, rt, sz[N], vis[N], mx, pre[N]; int dep[N], d[N], is[10000010], qq[10000010], ss[10000010]; struct node { int v, w, nt; } no[N]; void add(int u, int v, int w) { no[cnt] = node{v, w, h[u]}; h[u] = cnt++; } void getroot(int u, int fa) { sz[u] = 1; int ma = 0; for(int i = h[u]; ~i; i = no[i].nt) { int v = no[i].v; if(!vis[v] && v != fa) { getroot(v, u); sz[u] += sz[v]; ma = max(ma, sz[v]); } } ma = max(ma, sn - sz[u]); if(mx > ma) mx = ma, rt = u; } void getdep(int u, int fa) { d[++d[0]] = dep[u]; for(int i = h[u]; ~i; i = no[i].nt) { int v = no[i].v; if(!vis[v] && v != fa) dep[v] = dep[u] + no[i].w, getdep(v, u); } } void calc(int u) { int pp = 0; for(int i = h[u]; ~i; i = no[i].nt) { int v = no[i].v; if(!vis[v]) { d[0] = 0, dep[v] = no[i].w, getdep(v, u); for(int j = 1; j <= d[0]; j++) for(int k = 1; k <= m; k++) if(pre[k] >= d[j]) qq[k] |= is[pre[k] - d[j]]; for(int j = 1; j <= d[0]; j++) ss[pp++] = d[j], is[d[j]] = 1; } } for(int i = 0; i < pp; i++) is[ss[i]] = 0; } void dfs(int u) { vis[u] = is[0] = 1, calc(u); for(int i = h[u]; ~i; i = no[i].nt) { int v = no[i].v; if(!vis[v]) mx = 1e9, sn = sz[v], rt = 0, getroot(v, 0), dfs(rt); } } int main() { memset(h, -1, sizeof h); scanf("%d%d", &n, &m); for(int u, v, w, i = 1; i < n; i++) { scanf("%d%d%d", &u, &v, &w); add(u, v, w), add(v, u, w); } for(int i = 1; i <= m; i++) scanf("%d", &pre[i]); sn = n, mx = 1e9, getroot(1, 0), dfs(rt); for(int i = 1; i <= m; i++) if(qq[i]) printf("AYE\n"); else printf("NAY\n"); return 0; }