【模板】P3806 【模板】点分治1
很好的一道模板题，很无脑经典。
讲讲淀粉质吧，很营养，实际上，点分治是树上的分治算法。根据树的特性，树上两点的路径只有一下两种情况：
- 路径经过根((*))
- 路径不经过根((**))
显然对于((**))我们可以通过指定一个新的根使得((**))变成一个子问题。
那么我们在处理的时候，分两种情况：
- 处理自己各个子树之间的路径((-))
- 各个子树之内的路径((--))
显然((--))的问题可以通过递归((**))的子问题解决
那么有什么用呢？
考虑时间复杂度，我们指定新根时，若制定它的各自子树的重心，那么最多会递归(logn)次。这是淀粉质的营养时间基数。
那么，我们只需要设计在子树间进行统计答案的复杂度为(O(x))的算法，那么我们就可以做到(O(xlogn))的解决了。
这道模板题是问我们是否存在路径长度为(k)的路径，我们直接开桶把一个点到指定的(rt)的距离存下来，之后直接查询即可，这样的时间复杂度是(O(n))。
总时间复杂度(O(nlogn))
代码如下
#include<bits/stdc++.h>
using namespace std;
#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;++t)
#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)
#define ERP(t,a) for(register int t=head[a];t;t=e[t].nx)
#define Max(a,b) ((a)<(b)?(b):(a))
#define Min(a,b) ((a)<(b)?(a):(b))
#define midd register int mid=(l+r)>>1
#define TMP template < class ccf >
TMP inline ccf qr(ccf b){
char c=getchar();
int q=1;
ccf x=0;
while(c<48||c>57)
q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)
x=x*10+c-48,c=getchar();
return q==-1?-x:x;
}
const int maxn=1e4+15;
int n,m;
struct E{
int to,w,nx;
}e[maxn<<1];
int head[maxn];
int cnt;
inline void add(int fr,int to,int w,bool f){
e[++cnt]=(E){to,w,head[fr]};
head[fr]=cnt;
if(f)
add(to,fr,w,0);
}
bool usd[maxn];
int siz[maxn];
int spa[maxn];
int sav[maxn];
int d[maxn];
int rt;
int k[105];
bool ans[10000005];
bool tell[105];
int q[maxn];
int sum;
void dfsroot(int now,int last){
siz[now]=1;
spa[now]=0;
ERP(t,now){
if(e[t].to!=last&&!usd[e[t].to]){
dfsroot(e[t].to,now);
siz[now]+=siz[e[t].to];
spa[now]=Max(spa[now],siz[e[t].to]);
}
}
spa[now]=Max(spa[now],sum-siz[now]);
if(spa[now]<spa[rt]||rt==0)
rt=now;
}
void dfsdis(int now,int last,int ew){
d[now]=d[last]+ew;
sav[++sav[0]]=d[now];
ERP(t,now){
if(e[t].to!=last&&!usd[e[t].to]){
dfsdis(e[t].to,now,e[t].w);
}
}
}
inline void calc(int now){
register int p=0;
ERP(t,now){
if(!usd[e[t].to]){
sav[0]=0;d[now]=0;
dfsdis(e[t].to,now,e[t].w);
RP(j,1,m){
if(!tell[j]){
RP(i,1,sav[0]){
if(k[j]>=sav[i]){
if(ans[k[j]-sav[i]])
tell[j]=1;
}
}
}
}
RP(i,1,sav[0])
ans[sav[i]]=1;
RP(i,1,sav[0])
q[++p]=sav[i];
}
}
RP(t,1,p)
ans[q[t]]=0;
}
void solve(int now){
usd[now]=ans[0]=1;
calc(now);
ERP(t,now){
if(!usd[e[t].to]){
sum=siz[e[t].to];
rt=0;
dfsroot(e[t].to,0);
solve(rt);
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
n=qr(1);
m=qr(1);
for(register int t=1,t1,t2,t3;t<n;++t){
t1=qr(1);
t2=qr(1);
t3=qr(1);
add(t1,t2,t3,1);
}
RP(t,1,m)
k[t]=qr(1),tell[t]=!k?1:0;
sum=n;
dfsroot(1,0);
solve(rt);
RP(t,1,m)
if(tell[t])
puts("AYE");
else
puts("NAY");
return 0;
}