[luogu P3806] 【模板】点分治1
题目背景
感谢hzwer的点分治互测。
题目描述
给定一棵有n个点的树
询问树上距离为k的点对是否存在。
输入输出格式
输入格式：
n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径
接下来m行每行询问一个K
输出格式：
对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引号)
输入输出样例
说明
对于30%的数据n<=100
对于60%的数据n<=1000,m<=50
对于100%的数据n<=10000,m<=100,c<=1000,K<=10000000
首先这是点分裸题啊。。刷过点分的dalao都知道。
但似乎这题我只会calc里面n^2暴力扫？用不来m的100？
没事，让我们证明一下复杂度。。
T(n)=2T(n/2)+n^2。
然后我并不会主定理。。画了下二叉树图。
然后发现T(n)=2n^2（n^2+(1/2)n^2+(1/4)n^2+...）。
然后，因为n=10000，把常数写小一点，有点信仰就可以了。
code：
#include <cstdio> #include <cstring> #include <algorithm> #define ms(a,x) memset(a,x,sizeof a) using namespace std; ,D=; ],son[N<<],w[N<<]; int ro,subn,cnt,siz[N],mxs[N],dep[N],d[N]; int m,c[D]; bool vis[N]; void add (int x,int y,int z) { nxt[++tot]=lnk[x],lnk[x]=tot; son[tot]=y,w[tot]=z; } void dfs_size(int x,int p) { siz[x]=,mxs[x]=; for (int j=lnk[x]; j; j=nxt[j]) { if (son[j]==p||vis[son[j]]) continue; dfs_size(son[j],x); siz[x]+=siz[son[j]]; if (mxs[x]<siz[son[j]]) mxs[x]=siz[son[j]]; } if (mxs[x]<subn-mxs[x]) mxs[x]=subn-mxs[x]; if (mxs[x]<mxs[ro]) ro=x; } void dfs_depth (int x,int p) { dep[++cnt]=d[x]; for (int j=lnk[x]; j; j=nxt[j]) { if (son[j]==p||vis[son[j]]) continue; d[son[j]]=d[x]+w[j]; dfs_depth(son[j],x); } } void calc (int x,int v) { cnt=,dfs_depth(x,); ; i<cnt; ++i) { ; j<=cnt; ++j) { c[dep[i]+dep[j]]+=v; } } } void node_divide (int x) { ro=,dfs_size(x,),vis[ro]=; d[ro]=,calc(ro,); for (int j=lnk[ro]; j; j=nxt[j]) { if (vis[son[j]]) continue; calc(son[j],-); subn=siz[son[j]]; node_divide(son[j]); } } int main() { int x,y,z; scanf("%d%d",&n,&m); ; i<n; ++i) { scanf("%d%d%d",&x,&y,&z); add(x,y,z),add(y,x,z); } ro=,mxs[]=n,subn=n; node_divide(); ; i<=m; ++i) { scanf("%d",&x); printf(?"AYE":"NAY"); } ; }