bzoj 3528 [Zjoi2014]星系调查【树链剖分+数学】

参考：https://www.cnblogs.com/zhuohan123/p/3698852.html

首先，根据点到直线距离公式

\[d=\frac{kx_0-y_0+b}{\sqrt{k^{2}+1}}
\]

那么XPs的线性假设相斥度为

\[\delta =\frac{(kx_i-y_i+b)^{2}}{k^{2}+1}
\]

//以下部分为参考blog截图：

所以只需要维护\( \sum x_i , \sum y_i , \sum x_iy_i , \sum x_i^{2}, \sum y_i^{2} \)即可

注意到题目描述“使用这些跳跃星门，ZeusLeague+的物资就可以在这N个行星系中两两任意互相传输。由于经费问题，跳跃星门的个数不会超过行星系的个数。“也就是说，\( n-1\leq m\leq n \)，即，可能是一棵普通树或者基环树。

然后回到树上处理，首先定一个root（假设为1），预处理出所有点到root的\( \sum x_i ,\sum y_i,\sum x_iy_i,\sum x_i^{2},\sum y_i^{2} \)

对于普通树，采用树上差分的方法，即\( \delta_x+\delta_t-\delta_{lca(x,y)}-\delta_{father(lca(x,y))} \)

对于基环树，找到环上的两个点，bfs一遍，然后当成普通树处理即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

const int N=100005;

int n,m,Q,tot,tx[N],ty[N],h[N],cnt,id[N],q[N];

int si[N],hs[N],rt[N],fa[N],de[N],fr[N];

bool vis[N];

struct qwe

{

	int ne,to;

}e[N<<1];

struct dian

{

	int p[10];

	void add(int u,int v)

	{

		p[0]++;

		p[1]+=u;

		p[2]+=u*u;

		p[3]+=v;

		p[4]+=v*v;

		p[5]+=u*v;

	}

	double wk()

	{

		double A=p[2]-1.0*p[1]*p[1]/p[0],B=2*p[5]-2.0*p[1]*p[3]/p[0],C=p[4]-1.0*p[3]*p[3]/p[0];

		double a=4.0,b=-4.0*(A+C),c=4*A*C-B*B;

		return (-b-sqrt(b*b-4*a*c))/a/2;

	}

	dian operator + (dian x)

	{

		for(int i=0;i<6;i++)

			x.p[i]+=p[i];

		return x;

	}

	dian operator - (dian x)

	{

		for(int i=0;i<6;i++)

			x.p[i]=p[i]-x.p[i];

		return x;

	}

}a[N],b[N],u,v;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v)

{

	tot++;

	e[tot].ne=h[u];

	e[tot].to=v;

	h[u]=tot;

}

void dfs1(int u,int z,int fat)

{

	hs[u]=0;si[u]=1;fa[u]=fat;de[u]=de[fat]+1;

	vis[u]=1;rt[u]=z;

	a[u]=a[fa[u]];a[u].add(tx[u],ty[u]);

	for(int i=h[u];i;i=e[i].ne)

		if(!vis[e[i].to]&&e[i].to!=fat)

		{

			dfs1(e[i].to,z,u);

			si[u]+=si[e[i].to];

			if(si[e[i].to]>si[hs[u]])

				hs[u]=e[i].to;

		}

}

void dfs2(int u,int fir)

{

	fr[u]=fir;

	if(hs[u])

		dfs2(hs[u],fir);

	for(int i=h[u];i;i=e[i].ne)

		if(u==fa[e[i].to]&&e[i].to!=hs[u])//对于可能存在的环

			dfs2(e[i].to,e[i].to);

}

void cir()

{

	int x,y;

	memset(vis,0,sizeof(vis));

	for(x=1;x<=n;x++)

		for(int i=h[x];i;i=e[i].ne)

			if(e[i].to!=fa[x]&&fa[e[i].to]!=x)

			{

				y=e[i].to;

				if(de[x]>de[y])

					swap(x,y);

				for(;y!=x;y=fa[y])

				{

					q[++cnt]=y;

					id[y]=cnt;

					vis[y]=1;

					b[cnt]=b[cnt-1];

					b[cnt].add(tx[y],ty[y]);

				}

				q[++cnt]=x;

				id[x]=cnt;

				vis[x]=1;

				b[cnt]=b[cnt-1];

				b[cnt].add(tx[x],ty[x]);

				return;

			}

}

int lca(int u,int v)

{

	for(;fr[u]!=fr[v];de[fr[u]]>de[fr[v]]?u=fa[fr[u]]:v=fa[fr[v]]);

	return de[u]<de[v]?u:v;

}

int main()

{

	n=read(),m=read();

        if(m<n-1)//为了测试我对题意的理解是否正确……

	{

		cout<<23333;

		return 0;

	}

	for(int i=1;i<=n;i++)

		tx[i]=read(),ty[i]=read();

	for(int i=1;i<=m;i++)

	{

		int x=read(),y=read();

		add(x,y);add(y,x);

	}

	dfs1(1,1,0);

	memset(vis,0,sizeof(vis));

	if(n==m)

		cir();

	else

		q[cnt=1]=1;

	memset(fa,0,sizeof(fa));

	for(int i=1;i<=cnt;i++)

	{

		dfs1(q[i],q[i],0);

		dfs2(q[i],q[i]);

	}

	Q=read();

	while(Q--)

	{

		int x=read(),y=read();

		if(rt[x]==rt[y])

		{

			int lc=lca(x,y);

			u=a[x]+a[y]-a[lc]-a[fa[lc]];

			printf("%.5lf\n",u.wk());

		}

		else

		{

			if(id[rt[x]]>id[rt[y]])

				swap(x,y);

			u=a[x]-a[rt[x]]+a[y]-a[rt[y]]+b[id[rt[y]]]-b[id[rt[x]]-1];

			v=a[x]-a[rt[x]]+a[y]-a[rt[y]]+b[id[rt[x]]]+b[cnt]-b[id[rt[y]]-1];

			printf("%.5lf\n",min(u.wk(),v.wk()));

		}

	}

	return 0;

}

巴特西

bzoj 3528 [Zjoi2014]星系调查【树链剖分+数学】

最新文章

热门文章