题目分析: 树上点对问题首先想到点分治.假设我们进行了点分治并递归地解决了子问题.现在我们合并问题. 我们需要找到所有经过当前重心$ c $的子树路径.第一种情况是LCA为当前重心$ c $.考虑以$ 1 $为根的$ c $的子树.那么首先在子问题中先斥掉不经过$ c $的路径.然后对于$ c $的子树处理出距离数组.用桶存储. 从大到小枚举最大公因数$ d $,求出所有距离为$ d $倍数的点的个数.然后做乘法得到$ num1 $.再考虑$ num1 $中GCD不等于$ d $的数有哪些.实际
题意:给你一棵树,根节点为1,每条边长度为1.定义f(u,v)=gcd(u-lca(u,v),lca(u,v)-v),求有多少个无序点对f(u,v)=i.对每个i输出答案. n<=20W. 标程: #include<cstdio> #include<algorithm> #include<vector> using namespace std; typedef long long ll; ; int n,fa[N],f[N],g[N],sum[N],jp[N],d