自动搬运

查看原文

来自洛谷，原作者为

	zy AFO

搬运于2025-08-24 21:52:41，当前版本为作者最后更新于2021-04-27 20:45:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题目大意：

给定一棵节点为 $n$ 的树，$m$ 次操作，其中边权为 $c$ ，$c$ 为从 $u$点到 $v$ 点所改变值得倍数。

1. 改变 $x$ 及其子树的值。

2. 求 $x$ 点的值。

题外话: 数学课的灵感突现。$QwQ$

先考虑特殊情况：

• 先考虑这条树是一条链:

那就变成了一段序列，现在不就是区间更改和单点查询嘛，这不就是一个线段树的板子嘛！

于是我们就可以把这个问题再回到树上，按照时间戳来构造一个序列，在这个序列上进行操作。

但是我们会发现，区间更改的值不一样。

• 再考虑只在根节点上更改:

只需要将每个点加和再乘上前缀积。

那再考虑一般情况，我们只需要将更改的值除以该节点的前缀积，然后查询时再乘以该节点的前缀积就好。

于是我们就解决了区间更改的值不一样的问题。

现在我们有了大致的雏形。

$Dfs$ 将树转化为一个序列，找到每次修改的区间 $(dfn_x$ ~ $siz_x)$ ，并求出 $x$ 的前缀积 。

然后发现...他炸了。

关于砍树：

我们发现边权为 $0$ 的点会影响下面的节点的前缀积都为 $0$，更改时会出现除以 $0$ 的情况。

如果边权为 $0$ 的话，就不会对下面的节点产生影响，可以看成两棵树了，那么就砍掉这个边。 ·

void dfs(int x,int fa,double Mul)
{
	dfn[x]=siz[x]=++tim;				//找出修改的区间
	mul[x]=Mul;
	v[x]=1;
	for(int i=fir[x];i;i=nex[i]) {
		int p=poi[i];
		if(v[p]||p==fa)	continue;
		if(!val[i]) {
			rot[++rot[0]]=p;			//砍树
			continue;
		}
		dfs(p,x,Mul*val[i]);
		siz[x]=siz[p];
	}
}

剩下的就是线段树的部分了，没啥子好说的。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define N 200010
using namespace std;
int re() {
	int p=0; char i=getchar();
	while(i<'0'||i>'9')	i=getchar();
	while(i>='0'&&i<='9')	p=p*10+i-'0',i=getchar();
	return p;
}
int n,m,sum,tim;
int fir[N],nex[N],poi[N];
int rot[N],dfn[N],siz[N];
double val[N],mul[N];
bool v[N];
struct zy {
	int l,r;
	double sum;
	double lazy;
}e[N<<1];
void ins(int x,int y,double z) {
	nex[++sum]=fir[x];
	poi[sum]=y;
	val[sum]=z;
	fir[x]=sum;
}
void dfs(int x,int fa,double Mul)
{
	dfn[x]=siz[x]=++tim;
	mul[x]=Mul; v[x]=1;
	for(int i=fir[x];i;i=nex[i]) {
		int p=poi[i];
		if(v[p]||p==fa)	continue;
		if(!val[i]) {
			rot[++rot[0]]=p;
			continue;
		}
		dfs(p,x,Mul*val[i]);
		siz[x]=siz[p];
	}
}
void Build(int p,int l,int r) {
	e[p].l=l; e[p].r=r;
	if(l==r)	return;
	int mid=(l+r)>>1;
	Build(p<<1,l,mid);
	Build(p<<1|1,mid+1,r);
}
void Pushup(int p) {
	e[p].sum=e[p<<1].sum+e[p<<1|1].sum;
}
void Pushdown(int p)
{
	double	 Lazy=e[p].lazy;
	e[p<<1].lazy+=Lazy;
	e[p<<1|1].lazy+=Lazy;
	e[p<<1].sum+=(e[p<<1].r-e[p<<1].l+1)*Lazy;
	e[p<<1|1].sum+=(e[p<<1|1].r-e[p<<1|1].l+1)*Lazy;
	e[p].lazy=0;
}
void Update(int p,int l,int r,double d) {
	if(l<=e[p].l&&r>=e[p].r) {
		e[p].sum+=(e[p].r-e[p].l+1)*d;
		e[p].lazy+=d;
		return ;
	}
	if(e[p].lazy)	Pushdown(p);
	int mid=(e[p].l+e[p].r)>>1;
	if(l<=mid)	Update(p<<1,l,r,d);
	if(r>mid)	Update(p<<1|1,l,r,d);
	Pushup(p);
}
double Query(int p,int pos)
{
	if(e[p].l==e[p].r)
		return e[p].sum;
	if(e[p].lazy)	Pushdown(p);
	int mid=(e[p].l+e[p].r)>>1;
	double ans=0;
	if(pos<=mid) ans=Query(p<<1,pos);
	else  ans=Query(p<<1|1,pos);
	return ans;
}
int main()
{
	n=re(); 
	for(int i=1;i<n;i++) {
		int a,b; double c;
		a=re(); b=re(); scanf("%lf",&c);
		ins(a,b,c); ins(b,a,c);
	}
	rot[++rot[0]]=1;
	for(int i=1;i<=rot[0];i++) 
		dfs(rot[i],0,1);
	m=re();
	Build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int op=re();
		if(op==1) {
			int x=re();
			double k; scanf("%lf",&k);
			Update(1,dfn[x],siz[x],k/mul[x]);
		}
		else {
			int x=re();
			printf("%.8lf\n\n",Query(1,dfn[x])*mul[x]);
		}
	}
	return 0;
}

如有不妥，请不要吝啬您的评论！

话说，图片真的挺丑的！