题解 P3787 【冰精冻西瓜】
_zy_
·
·
题解
题目传送门
题目大意：
给定一棵节点为 n 的树，m 次操作，其中边权为 c ，c 为从 u 点到 v 点所改变值得倍数。
-
改变 x 及其子树的值。
-
求 x 点的值。
题外话: 数学课的灵感突现。QwQ
先考虑特殊情况：
那就变成了一段序列，现在不就是区间更改和单点查询嘛，这不就是一个线段树的板子嘛！
于是我们就可以把这个问题再回到树上，按照时间戳来构造一个序列，在这个序列上进行操作。
但是我们会发现，区间更改的值不一样。
只需要将每个点加和再乘上前缀积。
那再考虑一般情况，我们只需要将更改的值除以该节点的前缀积，然后查询时再乘以该节点的前缀积就好。
于是我们就解决了区间更改的值不一样的问题。
现在我们有了大致的雏形。
。
然后发现...他炸了。
**关于砍树：**
我们发现边权为 $0$ 的点会影响下面的节点的前缀积都为 $0$，更改时会出现除以 $0$ 的情况。
如果边权为 $0 $ 的话，就不会对下面的节点产生影响，可以看成两棵树了，那么就砍掉这个边。
·
```cpp
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];
}
}
```
剩下的就是线段树的部分了，没啥子好说的。
### 代码如下：
```cpp
#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;
}
```
**如有不妥，请不要吝啬您的评论！**
**~~话说，图片真的挺丑的！~~**