lp3806 【模板】点分治1

点分治是一种常常用于处理树上路径统计问题的算法。
首先我们可以想到这一题的一种简单的分治做法：找到一个点，从它开始搜，求出它的每一种长度。然后搜它的每一个子树，找到这些子树的根，求出它们的每一种长度并统计答案。
下面的问题便是要如何统计答案。容易想到的一种方案是枚举以某个点为根的链长两两相加得到的长度再容斥掉重复经过某一条边的路径，也就是所有经过它的同一个子节点的链对。
然而仔细想想这种做法的复杂度是有问题的。在菊花图上，它甚至会达到\(n^2\)的复杂度。故而我们必须另外考虑其他做法。
仔细观察数据范围，我们发现询问个数不超过100，这启发我们考虑一种\(O(nmlogn)\)的做法。
当我们求出以某个节点为根且经过前\(i\)个子节点的所有链以后，我们可以直接标记这这些长度的存在性，然后搜索经过第\(i+1\)个子节点的所有链，并枚举判断询问的长度减去这个链的长度剩下的长度是否存在。
这就做完了。

另：这题的数据是真的水。我犯了两个错，一个是没重设为局部大小，一个是找重心写挂了，而且用的还是复杂度错的算法，居然还过了…

#include<iostream>
#include<cstdio>

#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) 

inline int Max(int A,int B){
	return A>B?A:B;
}
struct ee{
	int v;
	int w;
	int nxt;
}e[20005];
int h[10005],et=0;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);Eadd(V,U,W);
}
int ans[10005]; 

int n,m,rt,s;

int mx[10005],sz[10005],vis[10005];
inline void dfs0(int X,int FA){
	sz[X]=1,mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],s-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
	}
}
int a[10005];
int dis[10005],tp=0;
inline void dfs2(int X,int FA){
	dis[++tp]=a[X];
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		a[e[i].v]=a[X]+e[i].w;
		dfs2(e[i].v,X);
	}
}
int exist[10000005],lst[10005],cnt=0,qry[10005];
inline void calc(int X){
	cnt=0;
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		a[e[i].v]=e[i].w;
		tp=0;
		dfs2(e[i].v,X);
		for(int j=1;j<=m;++j){
			for(int k=1;k<=tp;++k){
				(qry[j]-dis[k]>=0)?ans[j]|=exist[qry[j]-dis[k]]:0; 
			}
		}
		for(int j=1;j<=tp;++j){
			lst[++cnt]=dis[j];
			exist[dis[j]]=1;
		}
	}
	for(int i=1;i<=cnt;++i){
		exist[lst[i]]=0;
	}
}

inline void dfs1(int X){
	exist[0]=vis[X]=1;
	calc(X);
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		s=sz[X],rt=0;//记得重置根。 
		dfs0(e[i].v,X);
		dfs1(rt);
	}
}

void init(){
	scanf("%d%d",&n,&m);
	int u,v,w,x;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		qry[i]=x;
	}
	s=n,mx[0]=n,rt=0;
	dfs0(1,0);
	dfs1(rt);
	for(int i=1;i<=m;++i){
		puts(ans[i]?"AYE":"NAY");
	}
} 

int main(){
	init();
	return 0;
}