点分治

点分治

点分治可以解决树上大规模路径问题

过程 :

每次找出重心，处理出所有跨过重心的信息，例如将一条长$k$的路径拆成两条跨过重心的链，然后递归处理，只会递归$O(lo{g}_n)$层，总复杂度为$O(nlo{g}_n)$

小 $trick$ : 将每层处理的节点放入队列里，然后弹出队列清空，直接$memset$复杂度不对

例题：

Luogu 3806

没什么好说的，板子题，按照上面说的直接做就好了

代码 :

#include<bits/stdc++.h> using namespace std; namespace zzc { const int maxn = 1e4+5; const int maxm = 1e7+5; const int inf = 1e9+7; int head[maxn],que[maxn],dis[maxn],siz[maxn],maxx[maxn],d[maxn]; int n,ecnt,m,sum,rt,cnt; bool vis[maxn],ins[maxm],ans[maxn]; queue<int> tag; struct edge { int to,nxt,val; }e[maxn<<1]; void add(int u,int v,int w) { e[++ecnt].to=v; e[ecnt].val=w; e[ecnt].nxt=head[u]; head[u]=ecnt; } void calcsiz(int u,int fa) { siz[u]=1; maxx[u]=0; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(v==fa||vis[v]) continue; calcsiz(v,u); siz[u]+=siz[v]; maxx[u]=max(maxx[u],siz[v]); } maxx[u]=max(maxx[u],sum-siz[u]); if(maxx[u]<maxx[rt]) rt=u; } void calcdis(int u,int fa) { d[++cnt]=dis[u]; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(v==fa||vis[v]) continue; dis[v]=dis[u]+e[i].val; calcdis(v,u); } } void dfz(int u,int fa) { ins[0]=true; tag.push(0); vis[u]=true; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(v==fa||vis[v]) continue; dis[v]=e[i].val; calcdis(v,u); for(int j=1;j<=cnt;j++) { for(int k=1;k<=m;k++) { if(que[k]>=d[j]) ans[k]|=ins[que[k]-d[j]]; } } for(int j=1;j<=cnt;j++) { if(d[j]<=10000000) ins[d[j]]=true,tag.push(d[j]); } cnt=0; } while(!tag.empty()) ins[tag.front()]=false,tag.pop(); for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(v==fa||vis[v]) continue; sum=siz[v]; rt=0; maxx[rt]=inf; calcsiz(v,u); calcsiz(rt,-1); dfz(rt,u); } } void work() { int a,b,c; scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,c);add(b,a,c); } for(int i=1;i<=m;i++) scanf("%d",&que[i]); rt=0; sum=n; maxx[rt]=inf; calcsiz(1,-1); calcsiz(rt,-1); dfz(rt,-1); for(int i=1;i<=m;i++) { if(ans[i]) printf("AYE\n"); else printf("NAY\n"); } } } int main() { zzc::work(); return 0; }