lp3676 小清新数据结构题

传送门

Description

有一棵\(n\)个点的树，每个点有一个点权。

现在有\(q\)次操作，每次操作是修改一个点的点权或指定一个点，询问以这个点为根时每棵子树点权和的平方和。

Solution

我们设\(Sum=\sum_{i=1}^{n} w_i\),\(s_i\)表示\(i\)子树的权值和

发现不管根是哪个节点，\(W=\sum_{i=1}^n s_i(Sum-s_i)\)都是一个定值

因为它相当于对于每条边连接的两个联通块的”点权和的积“的和

所以，我们要求的\(\sum_{i=1}^{n} s_i^2=Sum*(\sum_{i=1}^n s_i)-W\)

考虑怎么计算\(calc(root)=\sum_{i=1}^{n} s_i\)

发现其实上就是\(Sum+\sum_{i=1}^n dis(root,i)*val_i\)

可以用点分树来维护

考虑怎么计算\(W\)

对于每次修改\(val_i+=delta\)，就有\(W+=\sum_{j=1}^n val_j*dis(i,j)*delta=delta*calc(i)\)

发现这道题本质和幻想乡战略游戏是一样的

可是把原来的代码交上去，就\(TLE\)了，只好考虑重构

不妨把过程重新理一遍：

点分树有一个性质，对于树上的两个点，它们的\(lca\)一定在两点在原树上的简单路径上

因此，要求两个点的实际距离，可以通过分别计算它们到\(lca\)的实际距离求和得到

考虑以上性质，我们可以设：

\(vsum_i\)表示\(i\)在点分树上的子树内的权值和

\(dis1_i\)表示 \(\sum_{j} dis(i,j)*val_j\)，\(j\)是\(i\)在点分树上的子树内的节点

\(dis2_i\)表示 \(\sum_{j} dis(par_i,j)*val_j\)

\(par_i\)是\(i\)在点分树上的父亲

\(dis1_i=\sum_{son} dis2_son\)，\(son\)是\(i\)在点分树上的儿子

\(calc(i)\)其实上就是枚举\(lca\)

\(lca=i\)时，和为\(dis1_i\)

\((\sum_{lca=par_j} dis1_{par_j}-dis2_j)\)算的是外围节点到\(lca\)的和

\(dis(i,par_j)*(vsum_{par_j}-vsum_j))\)算的是它们到\(i\)的和

我们发现，求距离的部分其实不需要像之前那样全部记下来，可以用\(RMQ\)求树上距离

具体来说，和\(RMQ\)求\(LCA\)差不多，只不过维护的最小值不是欧拉序，而是到根路径的长

Code

#include<bits/stdc++.h>

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define reg register

#define int ll

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

const int MN=2e5+5;

int n,m;

struct edge{int to,w,nex;}e[MN<<2];int en,hr[MN];

void ins(int x,int y,int w,int *h){e[++en]=(edge){y,w,h[x]};h[x]=en;}

int Val[MN],O,SUM;

struct Tree

{

    int Hr[MN],ind,st[MN<<2][21],dep[MN],pos[MN<<1],lg[MN<<2],_siz[MN];

    inline void Ins(int x,int y,int w){ins(x,y,w,Hr);ins(y,x,w,Hr);}

    int dis(int x,int y)

	{

        if(pos[x]>pos[y]) std::swap(x,y);

        reg int k=lg[pos[y]-pos[x]+1];

        return dep[x]+dep[y]-2*min(st[pos[x]][k],st[pos[y]-(1<<k)+1][k]);

    }

    void dfs(int x,int fa=0)

	{

        st[pos[x]=++ind][0]=dep[x];reg int i;

		for(i=Hr[x];i;i=e[i].nex)if(e[i].to^fa)

            dep[e[i].to]=dep[x]+e[i].w,dfs(e[i].to,x),st[++ind][0]=dep[x];

    }

    void get_O(int x=1,int fa=0)

	{

	    reg int i;_siz[x]=Val[x];

    	for(i=Hr[x];i;i=e[i].nex)if(e[i].to^fa)

   	 		get_O(e[i].to,x),_siz[x]+=_siz[e[i].to];

    	O+=1ll*(SUM-_siz[x])*_siz[x];

	}

    inline void pre_work()

	{

		reg int i,j;get_O();dfs(1);

    	for(lg[0]=-1,i=1;i<(MN<<2);i++)lg[i]=lg[i>>1]+1;

        for(j=1;j<20;++j)for(i=1;i+(1<<j)-1<=ind&&i<=ind;++i)

        st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);

    }

}T;

int sum,rt,mx[MN],vis[MN],par[MN],cnt,siz[MN];

ll dis1[MN],dis2[MN],sumv[MN];

void getrt(int x,int fa)

{

	siz[x]=1;mx[x]=0;reg int i;

	for(i=T.Hr[x];i;i=e[i].nex)if(!vis[e[i].to]&&(e[i].to!=fa))

		getrt(e[i].to,x),siz[x]+=siz[e[i].to],mx[x]=max(mx[x],siz[e[i].to]);

	mx[x]=max(mx[x],sum-siz[x]);

	if(mx[x]<mx[rt]) rt=x;

}

void _work(int x,int fa)

{

    vis[x]=1;par[x]=fa;reg int i;

    for(i=T.Hr[x];i;i=e[i].nex)if(!vis[e[i].to])

        mx[rt=0]=sum=siz[e[i].to],getrt(e[i].to,0),ins(x,rt,0,hr),_work(rt,x);

}

void pre_work()

{

	sum=mx[rt=0]=n;getrt(1,0);

	int tmp=rt;_work(rt,0);rt=tmp;

}

inline void Modify(int x,int val)

{

    sumv[x]+=val;reg int i,dis;

    for(i=x;par[i];i=par[i])

	{

        dis=T.dis(par[i],x);

        dis1[par[i]]+=dis*val;

        dis2[i]+=dis*val;

        sumv[par[i]]+=val;

    }

}

inline ll calc(int x)

{

    ll ans=dis1[x];reg int i,dis;

    for(i=x;par[i];i=par[i])

	{

        dis=T.dis(par[i],x);

        ans+=dis1[par[i]]-dis2[i];

        ans+=dis*(sumv[par[i]]-sumv[i]);

    }

    return ans;

}

signed main()

{

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

    reg int i,x,y;

    for(i=1;i<n;i++) x=read(),y=read(),T.Ins(x,y,1);

    pre_work();

	for(i=1;i<=n;++i) SUM+=Val[i]=read();

	T.pre_work();

    for(i=1;i<=n;++i) Modify(i,Val[i]);

    while(m--)

	{

		reg int opt=read();

    	if(opt==1)

    	{

    		x=read();y=read()-Val[x];Modify(x,y);

    		SUM+=y;O+=y*calc(x);Val[x]+=y;

        }

        else printf("%lld\n",SUM*(calc(read())+SUM)-O);

    }

    return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

lp3676 小清新数据结构题

传送门

Description

Solution

Code

最新文章

热门文章