题目链接

题目大意

给你一棵树，需要支持两个操作：

1.对于所有节点 \(v\) （包括 \(u\) 本身) 记 \(v\) 与 \(u\) 的简单路径长度为 \(d\) ，\(v\) 的权值增加 \(\frac{w}{\left \lfloor p^{d} \right \rfloor}\)

2.删除边 \(uv\) 并询问 \(u\) ，\(v\) 所在的联通块权值和（只是此次删除）

分析

操作1：

不好直接处理操作 \(1\)

所以将操作 \(1\) 转化为子树操作

记 \(W(u,w,p)\) 为对 \(u\) 的子树进行操作 \(1\)

那么原操作可以转化成：

\(W(u,w,p)\)

\(W(fa[u],\frac wp,p)W(u,\frac{w} {p^{2}},p)\)

(以此类推)

当 \(p\) 不等于 \(1\) 时此操作复杂度为 \(O\left ( logn \right )\)

当 \(p\) 为 \(1\) 时即为所有点都加 \(w\)

记录一个全局变量即可

操作2：

操作 \(2\) 可以转化为求子树和

对于每个 \(W\) 分别考虑

当 \(u\) 在子树内时

对答案的贡献即为该操作的贡献和

对于每个 \(W\) 将此次操作产生的贡献和记在 \(u\) 上

再利用树状数组维护子树和即可

当 \(u\) 为当前子树根节点的祖先时

记 \(vl\left [u\right]\left[i\right]\) 为此次操作对 \(u\) 的子树内到 \(u\) 为 \(i\) 的点的产生贡献和

\(num\left [u\right]\left[i\right]\) 为到 \(u\) 的子树内到 \(u\) 为 \(i\) 的点的个数

对答案的贡献则为 \(num[x][i]*vl[u][i+j]\) （ \(j\) 为 \(x\) 到 \(u\) 的距离）

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=200005;

int n,q;

int head[N],ne[N*2],v[N*2],tot=1;
void add(int x,int y){
	ne[++tot]=head[x];
	head[x]=tot;
	v[tot]=y;
}

int fa[N],dep[N],num[N][35],siz[N],dfn[N],cnt=0;
//siz为子树大小 dfn为dfs序
void dfs(int u,int fu){
	fa[u]=fu,dep[u]=dep[fu]+1,num[u][0]=1,dfn[u]=++cnt,siz[u]=1;
	for(int i=head[u];i;i=ne[i]){
		if(v[i]==fu) continue;
		dfs(v[i],u);
		for(int j=1;j<=30;j++) num[u][j]+=num[v[i]][j-1];
		siz[u]+=siz[v[i]];
	}
}

int all=0;//全局变量
int tr[N],vl[N][35];//树状数组
void addu(int x,int v){
	for(;x<=n;x+=(x&-x)) tr[x]+=v;
}
int ask(int x){
	int ans=0;
	for(;x;x-=(x&-x)) ans+=tr[x];
	return ans;
}

void M(int u,int w,int p){
	int ad=0;
	for(int i=0;i<=30&&w;i++,w/=p) ad+=num[u][i]*w,vl[u][i]+=w;
	addu(dfn[u],ad);
}

int Q(int x){
	int ans=all*siz[x];
	ans+=ask(dfn[x]+siz[x]-1)-ask(dfn[x]-1);//子树内的操作
	int v=fa[x];//祖先的操作
	for(int i=1;i<=30&&v;i++,v=fa[v]) for(int j=0;j+i<=30;j++) ans+=num[x][j]*vl[v][i+j];
	return ans;
}

signed main(){
	scanf("%lld %lld", &n, &q);
	for(int i=1;i<=n-1;i++){
		int x,y;
		scanf("%lld %lld", &x, &y);
		add(x,y);add(y,x);
	}
	
	dfs(1,0);
	
	for(int i=1;i<=q;i++){
		int k,u,w,p,v;
		scanf("%lld", &k);
		if(k==1){
			scanf("%lld %lld %lld", &u, &w, &p);
			if(p==1){ all+=w; continue;}
			M(u,w,p);
			while(w>0&&fa[u]>0){
				w/=p;
				M(fa[u],w,p);
				M(u,-w/p,p);
				u=fa[u];
			}
		}
		else{
			scanf("%lld %lld", &u, &v);
			int ans;
			if(dep[u]<dep[v]) ans=Q(v);
			else ans=Q(u);
			int an=Q(1)-ans;
			if(dep[u]<dep[v]) swap(ans,an);
			printf("%lld %lld\n", ans, an);
		}
	}
	return 0;
}