2016年计蒜之道初赛第2题

未分类

---

题意：
给定$n$个点的一颗树，树上每个点有个权值$a_i$，边的长度均为$1$，求所有互质的点对的距离的和.
对中等版本，有$1\leq n \leq 10^4,1\leq a_i \leq 500.$
对困难版本，有$1\leq n \leq 10^5,1\leq a_i \leq 10^5.$

题解：
对中等版本的数据：
考虑每条边的贡献，树上的每条边都会将树分成两个联通子树$T_1,T_2$，那么对$u\in T_1,v\in T_2$，如果$gcd(a_u,a_v)=1$，则会给答案造成$+1$的贡献.
考虑莫比乌斯反演，假设$b_i$表示$T_1$中点权为$i$的倍数的点的个数，$c_i$表示$T_2$中点权为$i$的倍数的点的个数，那么$T_1,T_2$给答案造成的贡献为：

$$\sum_{i=1}^{500}b_i*c_i*\mu(i)$$
$\mu(i)$表示$i$的莫比乌斯函数.
可以选一个点将树转换成有根树，记录$dfs$序，每一条边对应的两个子树中有一个是在$dfs$序中相邻的一块，可以用线段树辅助求解出$b_i,c_i$.
时间复杂度$O(max(a_i)nlogn)$，空间复杂度$O(max(a_i)n)$.
对困难版本的数据：
同样考虑用莫比乌斯反演来统计每条边的贡献，设$s_i$是全部点的点权中为$i$的倍数的个数，显然$s_i=b_i+c_i$，$s_i$可以被预先处理出来，所以上面的式子可以转化成：
$$\sum_{i=1}^{10^5}b_i(s_i-b_i)\mu(i)=\sum_{i=1}^{10^5}b_is_i\mu(i)-\sum_{i=1}^{10^5}b_i^2\mu(i)$$
考虑树上动态规划，每个点$u$记录$ans_1,ans_2,map<int,int>mp$，$接下来的b对应u的子树.$
$$\begin{align*} ans_1&=\sum_{i=1}^{10^5}s_i\mu(i)b_i \\ ans_2&=-\sum_{i=1}^{10^5}b_i^2\mu(i) \end{align*}$$
$mp$是一个映射，$mp(i)$在这里就是$b_i$，为了节省空间开销而使用.
维护以上三个结构就可以对两个节点的值进行合并，合并的时候使用启发式合并，也就是将小的暴力拆解拼到大的上面（这里大小指$mp$的大小）.
总时间复杂度是$O(nlognlog(max(a_i))$，空间复杂度是$O(nk)$，这里的$k=max_{i=1}^{10^5}d(i)$，$d(i)$是$i$的因子个数，根据程序运行计算可得$k=128$.
下面插入一段启发式合并的$C++$代码：

void union(Node& l,Node& r){
    if(l.size<r.size()) swap(l,r);
    l.ans1+=r.ans1;
    for(map<int,int>::iterator it=r.mp.begin();it!=r.mp.end();++it){
        int t1=l.mp[it->first],t2=t1+it->second;
        l.ans2+=mobius[it->first]*(1LL*t1*t1-1LL*t2*t2);
        l.mp[it->first]+=it->second;
    }
}