Luogu P3787 冰精冻西瓜

发表于 | 更新于 | 阅读次数：

题目背景

盛夏，冰之妖精琪露诺发现了一大片西瓜地，终于可以吃到美味的冻西瓜啦。

题目描述

琪露诺是拥有操纵冷气程度的能力的妖精，一天她发现了一片西瓜地。这里有 $n$ 个西瓜，由 $n-1$ 条西瓜蔓连接，形成一个有根树，琪露诺想要把它们冷冻起来慢慢吃。

这些西瓜蔓具有神奇的性质，可以将经过它的冷气的寒冷程度放大或缩小，每条西瓜蔓放大/缩小冷气寒冷程度的能力值为 $W_i$ ，表示冷气经过它后，寒冷程度值 $x$ 会变为 $x\times w_i$ 。每个西瓜也有一个寒冷程度值，炎热的夏日，所有西瓜的寒冷程度值初始都为 $0$ 。

琪露诺会做出两种动作:

①.对着西瓜 $i$ 放出寒冷程度为 $x$ 的冷气。这股冷气顺着西瓜蔓向“西瓜树”的叶子节点蔓延，冷气的寒冷程度会按照上面的规则变化。遇到一个西瓜连了多条西瓜蔓时，每条叶子节点方向的西瓜蔓均会获得与原先寒冷程度相等的冷气。途径的所有西瓜的寒冷程度值都会加上冷气的寒冷程度值。

⑨.向你询问西瓜 $i$ 的寒冷程度值是多少。

等等，为什么会有⑨？因为笨蛋琪露诺自己也会忘记放了多少冰呢。

所以，帮她计算的任务就这么交给你啦。

输入输出格式

输入格式：

第一行一个整数 $n$ ,表示西瓜的数量。

西瓜编号为 $1\sim n$ ， $1$ 为这棵“西瓜树”的根。

接下来 $n-1$ 行，每行有两个整数 $u,v$ 和一个实数 $w$ ，表示西瓜 $u$ 和西瓜 $v$ 之间连接有一条藤蔓，它放大/缩小冷气寒冷程度的能力值为 $w$ 。

接下来一行一个整数 $m$ ，表示操作的数量。

接下来 $m$ 行，每行两个或三个整数。

第一个数只能是 $1$ 或 $9$ 。

如果为 $1$ ，接下来一个整数 $i$ 和一个实数 $x$ ，表示对西瓜 $i$ 放出寒冷程度为 $x$ 的冷气。

如果为 $9$ ，接下来一个整数 $i$ ，表示询问编号为 $i$ 的西瓜的寒冷程度值。

输出格式：

对于每个操作⑨，输出一行一个实数，表示对应西瓜的寒冷程度值。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
4
1 2 1.00000000
2 3 0.00000000
3 4 1.00000101
9
1 1 3.00000000
9 2
9 3
1 2 1.42856031
9 4
9 2
1 3 4.23333333
9 2
9 4

输出样例#1：

1
2
3
4
5
6
3.00000000
0.00000000
0.00000000
4.42856031
4.42856031
4.23333761

说明

子任务可能出现如下的特殊性质:

“西瓜树”退化为一条链

输入数据中的实数均保留 $8$ 位小数，选手的答案被判作正确当且仅当输出与标准答案误差不超过 $10^-7$ 。请特别注意浮点数精度问题。

实际数据中，冷气的寒冷程度 $x$ 的范围为 $[-0.1,0.1]$

$($样例中的冷气寒冷程度的范围为 $[1,5]$ $)$

题解

这题还蛮毒瘤的，我交了 $20$ 次才过...$($其实因为我线段树打炸了没发现$)$

一开始看到这题想到暴力，看到数据立马去世。

于是我想到了线段树。

因为有些边是 $0$ ，我们就把这棵树切成很多棵树遍历。

然后我是这么想的，先把树遍历一下，预处理出每个点到其树根的所有 $w$ 之积 $w[i]$ 。然后假设所有冷气都是由根传来的，那么在第 $i$ 个结点释放 $x$ 的冷气就相当于在根节点释放 $x/w[i]$ 的冷气。

然后接下来只需要区间更新就行了。这里我用了线段树。区间具体是怎么划分的呢？每个点所管辖的区间即是他所有子节点及其本身。我们在遍历的时候可以把 $i$ 所管辖的区间的最后一个数 $right[i]$ 求出来。

查询其实就是单点查询，将该节点的值乘上该节点的 $w[i]$ 就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
#define N 1000000
#define ld long double
using namespace std;
struct Edge{
	int from,to,next;
	ld dis;
}edge[N+5];
int n,m,num_edge,num_node,num_root;
int head[N+5],node[N+5],root[N+5],r[N+5];
ld w[N+5],addsum[4*N+5],tree[4*N+5];
bool vis[N+5];
void add_edge(int from,int to,ld dis){
	edge[++num_edge].next=head[from];
	edge[num_edge].from=from;
	edge[num_edge].to=to;
	edge[num_edge].dis=dis;
	head[from]=num_edge;
}
void dfs(int i,ld dis){
	if(vis[i])return;
	vis[i]=true;
	node[i]=++num_node;
	w[i]=dis;
	int p=head[i];
	while(p){
		if(!edge[p].dis)
			{if(!vis[edge[p].to])root[++num_root]=edge[p].to;}
		else dfs(edge[p].to,dis*edge[p].dis);
		p=edge[p].next;
	}
	r[i]=num_node;
}
void pushdown(int k){
	if(!addsum[k])return;
	addsum[k<<1]+=addsum[k];
	addsum[k<<1|1]+=addsum[k];
	tree[k<<1]+=addsum[k];
	tree[k<<1|1]+=addsum[k];
	addsum[k]=0; 
}
ld query(int k,int l,int r,int x){
	pushdown(k);
	if(l==r&&x==l)return tree[k];
	int mid=(l+r)>>1;
	if(x<=mid)return query(k<<1,l,mid,x);
	else return query(k<<1|1,mid+1,r,x);
}
void add(int k,int l,int r,int x,int y,ld v){
	if(l>y||r<x)return;
	pushdown(k);
	if(l>=x&&r<=y){
		addsum[k]+=v;
		tree[k]+=v;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=x)add(k<<1,l,mid,x,y,v);
	if(mid<y)add(k<<1|1,mid+1,r,x,y,v);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;
		ld d;
		scanf("%d%d%Lf",&u,&v,&d);
		add_edge(u,v,d);
		add_edge(v,u,d);
	}
	root[++num_root]=1;
	for(int i=1;i<=num_root;i++)dfs(root[i],1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int k,I;
		ld x;
		scanf("%d",&k);
		if(k==1){
			scanf("%d%Lf",&I,&x);
			add(1,1,n,node[I],r[I],x/w[I]);
		}
		else{
			scanf("%d",&I);
			printf("%.8Lf\n",query(1,1,n,node[I])*w[I]);
		}
	}
	return 0;
}