[CF494D]Birthday

题意：给一棵带边权的树，定义如下的一些东西

$S(x)$表示以$x$为根的子树中的节点组成的集合

$d(u,v)$表示$u$和$v$之间的距离

$f(u,v)\sum\limits_{x\in S(v)}d(u,x)^2-\sum\limits_{x\notin S(v)}d(u,x)^2$

多次询问求$f(u,v)$的值，对$10^9+7$取模至非负数

非常妙的树D！这个题啊，excited!

首先它涉及到了子树，我们当然要先dfs一次求出$dsum_i=\sum\limits_{x\in S(i)}d(i,x)$，$dsum2_i=\sum\limits_{x\in S(i)}d(i,x)^2$，子树大小$siz_i$和每个节点到根的距离$dis_i$

这个转移比较简单，设$son(x)$表示$x$的儿子组成的集合

考虑从$son(i)$转移到$i$，（以下均有$x\in son(i)$）

$\begin{align*}dsum_i&=\sum\limits_{x\in S(i),x\ne i}d(x,i)\\&=\sum\limits_{x\in S(i),x\ne i}d(x,k)+d(k,i)\\&=\sum\limits_{k\in son(i)}\left(dsum_k+siz_k\cdot d(k,i)\right)\end{align*}$

$\begin{align*}dsum2_i&=\sum\limits_{x\in S(i),x\ne i}d(i,x)^2\\&=\sum\limits_{x\in S(i),x\ne i}(d(x,k)+d(k,i))^2\\&=\sum\limits_{x\in S(i),x\ne i}(d(x,k)^2+2\cdot d(x,k)\cdot d(k,i)+d(k,i)^2)\\&=\sum\limits_{k\in son(i)}\left(dsum2_k+2\cdot d(k,i)\cdot dsum_k+siz_k\cdot d(k,i)^2\right)\end{align*}$

下一步，因为询问涉及到全局，所以我们要再dfs一次求出$alld_i=\sum\limits_{1\leq j\leq n}d(i,j)$，$alld2_i=\sum\limits_{1\leq j\leq n}d(i,j)^2$

因为题目钦定了说明了$1$是根，所以$alld_1=dsum_1,alld2_1=dsum2_1$

考虑从$i$转移到$son(i)$，（以下均有$x\in son(i)$）

$\begin{align*}alld_x&=\sum\limits_{j\in S(x)}d(x,j)+\sum\limits_{j\notin S(x)}d(x,j)\\&=\sum\limits_{j\in S(x)}\left(d(i,j)-d(x,i)\right)+\sum\limits_{j\notin S(x)}\left(d(i,j)+d(x,i)\right)\\&=alld_i-siz_x\cdot d(x,i)+(n-siz_x)\cdot d(x,i)\\&=alld_i+(n-2\cdot siz_x)\cdot d(x,i)\end{align*}$

$\begin{align*}alld2_x&=\sum\limits_{j\in S(x)}d(x,j)^2+\sum\limits_{j\notin S(x)}d(x,j)^2\\&=\sum\limits_{j\in S(x)}(d(i,j)-d(x,i))^2+\sum\limits_{j\notin S(x)}(d(i,j)+d(x,i))^2\\&=\sum\limits_{j\in S(x)}(d(i,j)^2-2\cdot d(i,j)\cdot d(x,i)+d(x,i)^2)+\sum\limits_{j\notin S(x)}(d(i,j)^2+2\cdot d(i,j)\cdot d(x,i)+d(x,i)^2)\\&=alld2_i-2\cdot d(x,i)\cdot(\sum\limits_{j\in S(x)}d(i,j)-\sum\limits_{j\notin S(x)}d(i,j))+n\cdot d(x,i)^2\\&=alld2_i+n\cdot d(x,i)^2-2\cdot d(x,i)\cdot(\sum\limits_{j\in S(x)}d(i,j)-(alld_i-\sum\limits_{j\in S(x)}d(i,j)))\\&=alld2_i+n\cdot d(x,i)^2-2\cdot d(x,i)\cdot(2(dsum_x+siz_x\cdot d(x,i))-alld_i)\end{align*}$

预处理出这些东西之后，看一看如何计算答案

首先当然要求一下lca，直接上倍增

#1若$u\notin S(v)$（$lca(u,v)\ne v$）

$\sum\limits_{x\notin S(v)}d(u,x)^2=alld2_u-\sum\limits_{x\in S(v)}d(u,x)^2$

$\begin{align*}\sum\limits_{x\in S(v)}d(u,x)^2&=\sum\limits_{x\in S(v)}(d(u,v)+d(v,x))^2\\&=siz_v\cdot d(u,v)^2+2\cdot d(u,v)\cdot\sum\limits_{x\in S(v)}d(v,x)+\sum\limits_{x\in S(v)}d(v,x)^2\\&=siz_v\cdot d(u,v)^2+2\cdot d(u,v)\cdot dsum_v+dsum2_v\end{align*}$

#2若$u\in S(v)$（$lca(u,v)=v$）

$\begin{align*}\sum\limits_{x\notin S(v)}d(u,x)^2&=\sum\limits_{x\notin S(v)}(d(u,v)+d(v,x))^2\\&=(n-siz_v)\cdot d(u,v)^2+2\cdot d(u,v)\cdot\sum\limits_{x\notin S(v)}d(v,x)+\sum\limits_{x\notin S(v)}d(v,x)^2\\&=(n-siz_v)\cdot d(u,v)^2+2\cdot d(u,v)\cdot(alld_v-dsum_v)+alld2_v-dsum2_v\end{align*}$

然后就ok啦，写转移真是烧脑啊

#include<stdio.h>
#define mod 1000000007ll
#define ll long long
ll mo(ll x){return x%mod;}
struct edge{
	int to,nex;
	ll v;
}e[200010];
ll dsum[100010],dsum2[100010],alld[100010],alld2[100010],siz[100010],dis[100010];
int h[100010],fa[100010][17],dep[100010],tot,n;
void add(int a,int b,ll c){
	tot++;
	e[tot].to=b;
	e[tot].v=c;
	e[tot].nex=h[a];
	h[a]=tot;
}
void dfs(int x){
	siz[x]=1;
	for(int i=h[x];i;i=e[i].nex){
		if(e[i].to!=fa[x][0]){
			dis[e[i].to]=mo(dis[x]+e[i].v);
			fa[e[i].to][0]=x;
			dep[e[i].to]=dep[x]+1;
			dfs(e[i].to);
			siz[x]+=siz[e[i].to];
			dsum[x]=mo(dsum[x]+dsum[e[i].to]+siz[e[i].to]*e[i].v);
			dsum2[x]=mo(dsum2[x]+mo(e[i].v*e[i].v)*siz[e[i].to]+2ll*e[i].v*dsum[e[i].to]+dsum2[e[i].to]);
		}
	}
}
void dfs2(int x){
	for(int i=h[x];i;i=e[i].nex){
		if(e[i].to!=fa[x][0]){
			alld[e[i].to]=mo(alld[x]+(n-2ll*siz[e[i].to])*e[i].v);
			alld2[e[i].to]=mo(alld2[x]+2ll*e[i].v*mo(alld[x]-2ll*dsum[e[i].to]-siz[e[i].to]*e[i].v)+(n-2ll*siz[e[i].to])*mo(e[i].v*e[i].v));
			dfs2(e[i].to);
		}
	}
}
void swap(int&a,int&b){
	int c=a;
	a=b;
	b=c;
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	int i;
	for(i=16;i>=0;i--){
		if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	}
	if(x==y)return x;
	for(i=16;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int main(){
	int q,i,j,u,v,uv;
	ll w;
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d%d%I64d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dep[1]=1;
	dfs(1);
	alld[1]=dsum[1];
	alld2[1]=dsum2[1];
	dfs2(1);
	for(j=1;j<17;j++){
		for(i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];
	}
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&u,&v);
		uv=lca(u,v);
		if(uv==v){
			w=mo(dis[u]-dis[v]);
			w=mo((n-siz[v])*mo(w*w)+2ll*w*(alld[v]-dsum[v])+alld2[v]-dsum2[v]);
			w=mo(alld2[u]-2ll*w);
		}else{
			w=mo(dis[u]+dis[v]-2ll*dis[uv]);
			w=mo(siz[v]*mo(w*w)+2ll*w*dsum[v]+dsum2[v]);
			w=mo(2ll*w-alld2[u]);
		}
		printf("%I64d\n",mo(w+mod));
	}
}

巴特西

[CF494D]Birthday

最新文章

热门文章