前言
给出一种线性(不算建虚树)的不用换根的做法 by ds,代码好写但是推导和证明有一定难度。
思路
定义 $S_v=$ 以 $v$ 为一条路线端点的合法方案数,则:
定义 $g(v,u)=$ 与路径 $v\to u$ 不相交的路径数量,则:
定义:
- $W_v=$ 完全不经过点 $v$ 的路径数量。
- $E_v=$ 完全不使用边 $(v,fa(v))$ 的路线数。
对于一条路线 $P=v\to u$,有:
证明
删掉 $P$ 上的点,剩下的每个连通块都”挂”在某个 $(x,\text{方向})$ 上,其中 $x\in P$ 且该方向不被 $P$ 使用;一条不与 $P$ 相交的线路必须整体落在某一个这样的连通块里。
对 $x\in P$ 记 $R(x,d)$ 为”从 $x$ 沿方向 $d$ 那一侧连通块内的线路数”,则
把 $P$ 上所有边的 $E$ 相加,每条边贡献两端方向的 $R$,合起来正好是”$P$ 在每个点上用到的那些方向的 $R$ 之和”。
相减后剩下的就是”没被用到的方向的 $R$ 之和”,也就是与 $P$ 不相交的线路数。$\blacksquare$
对 $W,E$ 使用树上前缀和,再加上 LCA 就可以 $O(1)/O(\log)$ 求 $g(v,u)$,问题转化为求 $W,E$。
记 $s_{v,c}$ 表示子树 $v$ 内颜色为 $c$ 的点的个数。
- 完全在子树 $v$ 内的路线:$w_I[v]=\sum_{c}\binom{s_{v,c}}{2}$,可以用虚树求(见下文)
- 恰好一个端点在子树 $v$ 内的路线:
证明
根据恒等式 $x^2=x+x(x-1)=x+2\binom{x}{2}$ 可得:
其中第一项等于 $sz_v$,第二项等于 $2w_I[v]$,即:
所以:
- 两端都在子树外的路线:
- 所以:
建虚树求 $wI$
对于每种颜色 $c$ 建虚树 $T_c$,按“LCA 恰为 $x\in T_c$ 的同色点对数”统计再求和:
把这个累加到 $f[x]$,所有颜色做完后在原树上做子树和即可:
总复杂度 $O(n\log n)$。
现在只需要计算 $S_v$。
thinking
这一步可以虚树上换根,但是写起来太麻烦了。考虑根号分治,轻色可以直接 $O(cnt_c^2)$ 求,不过需要写 $O(1)$ LCA。重色则可以通过推式子做到 $O(n)$。总复杂度就是 $O(n\sqrt n)$ 的,实测块长 $B=600$ 时跑的飞快:link。
但是其实完全可以在虚树上推式子,做到不用换根也能 $O(n)$。
记 $pW,pE$ 为 $W,E$ 的树上前缀和数组(从根到 $v$ 的和),$l=lca(v,u)$,则:
记 $A_x=pW_x-pE_x,h_x=W_x-2A_x$,则:
于是对于一种颜色 $C$,对于 $v\in C$ 有:
令 $T_v=\sum_{u\in C,u\neq v}h_{lca(v,u)}$,则:
前两项都好求,现在只需要求 $T_v$。
对于颜色 $C$ 和点 $v\in C$,记
记点 $v$ 到根的路径为 $r_0=root,r_1,\dots,r_d=v$,则有:
(令 $q_{r_{d+1}}=0$)
证明
即在两点的 LCA 处统计。满足 $lca(v,u)=r_j$ 的 $u$ 共有 $q_{r_j}-q_{r_{j+1}}$ 个。
然后做一些推式子,类似将 $q$ 主元:
说明
其中 $q_{r_{d+1}}=0$ 让第二项消失,$q_{r_0}=cnt_c$ 把根项提出来。
由于这个求和包含了 $u=v$ 的情况,所以下面计算 $T_v$ 的时候需要减去 $h_v$。
所以:
$ps$ 可以用树上前缀和求,直接在原树上求就是 $O(nk)$ 的,但可以把这个放到虚树上推。
为什么 $ps$ 能放到虚树上求
设 $y$ 的虚父亲是 $p$。对原树上 $p\to y$ 路径上严格居中的点 $x$,必有 $q_x=q_y$。
证明. 反设存在 $u\in C$ 且 $u\in sub(x)\setminus sub(y)$。取 $y$ 虚子树中的任一同色点 $w$(虚树每个节点下方至少有 $C$ 中的一个点),则 $\mathrm{lca}(u,w)=x$;而虚树点集对所有同色点对的 LCA 封闭,所以 $x$ 应为虚树节点,这与”$y$ 是 $p$ 的虚儿子”矛盾。$\blacksquare$
于是
(第二个等号用了 $q_x\equiv q_y$,第三个用了 $\sum\Delta h$ 的望远镜。)
虚根:若 $C$ 中有点在虚根子树之外,则虚根不是所有同色点的 LCA,矛盾;故根到虚根一段全是 $q_x=cnt_C$,得 $ps_{\text{虚根}}=cnt_C\cdot h_{\text{虚根}}$。
具体做法
虚树可以复用之前求 $wI$ 时建的。
对于每种颜色 $C$:
- 在虚树上自底向上求 $q_x$。
- 记 $sumA_C=\sum_{u\in C}A_u$,令 $ps_{虚根}=cnt_C\cdot h_{虚根}$,即可自顶向下求。
- 对于 $v\in C$:
总复杂度 $O(n)$。
代码
虚树可以复用,而且不用显式的建出来,直接按 dfn 序到序遍历即可。然后各种地方都可以用 dfn 序正序或倒序遍历,就不用写 dfs 了。
我写了个 $O(1)$ LCA,所以代码的复杂度瓶颈在建虚树的排序和二分,需要 $O(n\log n)$,其余的就按着式子写,都是线性的。
#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<#x":"<<(x)<<' '
#define dbe(x) cerr<<#x":"<<(x)<<'\n'
#define eb emplace_back
#define ep emplace
#define endl '\n'
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using tp=tuple<int,int>;
int main(){
// freopen("route.in","r",stdin);
// freopen("route.out","w",stdout);
cin.tie(0)->sync_with_stdio(0);
int n,m,k;
cin>>n>>m>>k;
vi c(n+1);
for(int i=1;i<=n;i++)cin>>c[i];
vector<vi>G(n+1);
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
G[u].eb(v),G[v].eb(u);
}
vi dfn(n+1),dep(n+1),fa(n+1),ds(n+1),fst(n+1),lg;// ds 为 dfn 序列
const int KMX=18;
vector<vi>st(KMX+1);/*erase fa*/{
vi eu;eu.reserve(n*2);
int dfncnt=0;
auto dfs=[&](int u,int f,auto&&dfs)->void {
if(f)G[u].erase(find(G[u].begin(),G[u].end(),f));
dfn[u]=++dfncnt,dep[u]=dep[f]+1,fa[u]=f,ds[dfncnt]=u;
fst[u]=eu.size(),eu.eb(u);
for(int v:G[u])dfs(v,u,dfs),eu.eb(u);
};dfs(1,0,dfs);
int m=eu.size();
for(vi&v:st)v.resize(m);
for(int i=0;i<m;i++)st[0][i]=eu[i];
for(int k=1;k<=KMX;k++){
for(int i=0;i+(1<<k)-1<m;i++){
int a=st[k-1][i],b=st[k-1][i+(1<<(k-1))];
st[k][i]=(dep[a]<dep[b]?a:b);
}
}
lg.resize(m+1);
for(int i=2;i<=m;i++)lg[i]=lg[i/2]+1;
}
auto LCA=[&](int u,int v){// O(1) LCA
int a=fst[u],b=fst[v];if(a>b)swap(a,b);
int k=lg[b-a+1];
int x=st[k][a],y=st[k][b-(1<<k)+1];
return dep[x]<dep[y]?x:y;
};
vector<vi>V(k+1),Pv(k+1);vi cnt(k+1);{//build v-tree; V: v-tree, sort by dfn; Pv: v-tree father
for(int i=1;i<=n;i++)V[c[ds[i]]].eb(ds[i]);// 按 dfn 序加入节点,可以省去一次 sort
for(int i=1;i<=k;i++)cnt[i]=V[i].size();
for(int i=1;i<=k;i++){// 两遍 sort 建虚树
int m=V[i].size();
if(m<2)continue;
vi&p=V[i];
for(int j=1;j<m;j++)p.eb(LCA(p[j-1],p[j]));
sort(p.begin(),p.end(),[&](int x,int y){return dfn[x]<dfn[y];});
p.resize(unique(p.begin(),p.end())-p.begin());
m=p.size();Pv[i].resize(m);
for(int j=0;j+1<m;j++){
int lca=LCA(p[j],p[j+1]);
Pv[i][j+1]=lower_bound(p.begin(),p.end(),lca,[&](int x,int y){
return dfn[x]<dfn[y];
})-p.begin();
}
}
}
vl W(n+1),E(n+1);{
vl wI(n+1);{
for(int i=1;i<=k;i++){
int m=V[i].size();
if(m<2)continue;
vi sz(m);vl cnt(m);
for(int j=m-1;j>=0;j--){
int u=V[i][j];
sz[j]+=(c[u]==i),cnt[j]+=ll(sz[j]-1)*sz[j]/2;
wI[u]+=cnt[j];
if(j)sz[Pv[i][j]]+=sz[j],cnt[Pv[i][j]]-=ll(sz[j]-1)*sz[j]/2;
}
}
for(int i=n;i>=1;i--)for(int v:G[ds[i]])wI[ds[i]]+=wI[v];
}
vi sz(n+1,1);for(int i=n;i>=1;i--)sz[fa[ds[i]]]+=sz[ds[i]];
vl wsum(n+1);for(int i=n;i>=1;i--)wsum[fa[ds[i]]]+=(wsum[ds[i]]+=cnt[c[ds[i]]]);
vl cross(n+1);for(int i=1;i<=n;i++)cross[i]=wsum[i]-sz[i]-2*wI[i];
ll R=0;for(int i=1;i<=k;i++)R+=ll(cnt[i]-1)*cnt[i]/2;
vl wO(n+1);for(int i=1;i<=n;i++)wO[i]=R-wI[i]-cross[i];
W=wO;for(int i=n;i>=1;i--)W[fa[ds[i]]]+=wI[ds[i]];
for(int i=1;i<=n;i++)E[i]=wI[i]+wO[i];
}
vl pW=W,pE=E;{
for(int i=1;i<=n;i++){
int u=ds[i];
pW[u]+=pW[fa[u]],pE[u]+=pE[fa[u]];
}
}
vl S(n+1);{
vl A(n+1),h(n+1),sumA(n+1);
for(int i=1;i<=n;i++)A[i]=pW[i]-pE[i],h[i]=W[i]-2*A[i],sumA[c[i]]+=A[i];
vi q(n+1);vl ps(n+1);
for(int i=1;i<=k;i++){
int m=V[i].size();
if(m<2)continue;
ll C=cnt[i];
for(int j=0;j<m;j++)q[V[i][j]]=(c[V[i][j]]==i);
for(int j=m-1;j>0;j--)q[V[i][Pv[i][j]]]+=q[V[i][j]];
ps[V[i][0]]=C*h[V[i][0]];
for(int j=1;j<m;j++){
int y=V[i][j],z=V[i][Pv[i][j]];
ps[y]=ps[z]+(ll)q[y]*(h[y]-h[z]);
}
for(int j=0;j<m;j++){
int v=V[i][j];
if(c[v]==i)S[v]=(C-2)*A[v]+sumA[i]+ps[v]-h[v];
}
}
}
ll ans;{
__int128 sum=0;//sum S > LONG_LONG_MAX
for(int i=1;i<=n;i++)sum+=S[i];
ans=sum/4;
}
cout<<ans<<endl;
while(m--){
int x;cin>>x;
cout<<ans-S[x]<<endl;
}
return 0;
}