因为jg记录的是曾经处理过的距离,所以在每次的合法路径判断完后,我们需要把当前处理出的dis加入到jg中标记,把当前这个根节点rt处理完后还要清空jg数组,因为jg数组是对于当前rt结点的.在清空jg数组时不要直接用memset,否则你有可能会TLE,应该用个队列或栈之类的把使用过的距离存起来,用过数组的哪个位置就清空那个位置.
我们已经知道了如何计算路径距离,如何判断合法路径,那么这就足够了吗?假设输入的数据是一条链,而我们一开始是随机找的根结点,那么最坏情况下选了这条链的端点的话这颗树的深度就为n,需要递归处理n层,所以我们的根不能随便选.为了让处理的子树深度尽可能小,所以我们每次选择树的重心.这样数的深度是logn的,递归处理也就只需要logn层.那么怎么如何找到重心呢?我们先来看看重心的定义:树的重心就是最大子树结点数最小的点.所以我们要统计子树结点数,接着要统计出一个结点的最大子树结点数(这里的最大子树结点数不仅包括当前根向下的子树,还包括向上的子树,上面子树的求法就是总点数减去向下子树的点数),然后要维护一个最大子树结点数最小的点.这些信息可以在dfs回溯时记录.类似求树的直径,求两次dfs,先找一个点dfs得到一个根,再用这个根dfs找出树的重心.
这里还需要注意一个问题,在点分治中,每处理完一个结点后就要删去这个结点以防止重复计算,那么总结点数是会改变的,每次重新选择根结点后要更新总点数,那么这个总点数是多少呢?就是siz[u],即上次找重心时这个点u的子树大小.为什么呢?因为你这次处理完后rt结点删掉了,那么点u和rt的路径就断掉了,以u为根节点的子树就成为了一个连通块,那么这个连通块的大小就是以u为根节点的子树的大小siz[u].
接下来我们来看下代码
main函数
1 int main(){ 2 int a,b,c; 3 scanf("%d%d",&n,&m); 4 for(int i=1;i<=n-1;i++){ 5 scanf("%d%d%d",&a,&b,&c); 6 add(a,b,c); 7 add(b,a,c); 8 } 9 for(int i=1;i<=m;i++){ 10 scanf("%d",&K[i]); 11 } 12 getroot(1,-1,n); 13 dfz(rt); 14 for(int i=1;i<=m;i++){ 15 if(ans[i])printf("AYE\n"); 16 else printf("NAY\n"); 17 } 18 }