冰精冻西瓜

题目

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

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

琪露诺会做出两种动作:

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

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

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

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

输入输出格式

输入格式:

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

西瓜编号为1~n,1为这棵“西瓜树”的根。

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

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

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

第一个数只能是1或9。

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

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

输出格式:

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

输入输出样例

输入样例

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

输出样例

3.00000000

0.00000000

0.00000000

4.42856031

4.42856031

4.23333761

思路

如果将树变成链 然后对链进行操作

对于一条链如果说要进行区间修改以及单点查询 很显然可以利用差分+树状数组搞定

关键在于如何将树弄成一条链

对于一条如果边权为0 可以直接将这条边砍掉 我们再对每一个根节点进行dfs序 同时记录以当前节点为根的子树在链中的左端点和右端点记录下来 以及从根节点到当前节点的w累乘

如果并不是在根节点放冷气那么可以将 释放的冷气/当前节点的w值 然后在从当前节点开始释放即可

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
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#define N 200000
#define M N*3
using namespace std;
inline int Max(int x, int y) {return x >= y ? x : y;}
inline int Min(int x, int y) {return x <= y ? x : y;}
inline int lowbit(int x) {return x & (-x);}
struct node{
int to, Next;double value;
}G[M];
int n, m, tot, h[N], root[N], cnt[N], Time;
int l[N], r[N];
double Q[M], W[N];
queue<int> q;
inline void add(int u, int v, double w) {tot ++; G[tot].to = v; G[tot].value = w; G[tot].Next = h[u]; h[u] = tot;}
void dfs(int x, double t)
{
W[x] = t;
cnt[x] = ++ Time;
l[x] = Time;
for (int i=h[x]; i; i=G[i].Next)
{
int v = G[i].to;
if (!cnt[v] && !G[i].value) {q.push(v); root[v] = 1; continue;}
if (!cnt[v])
{
dfs(v, t * G[i].value);
}
}
r[x] = Time;
}
inline void add(int x, double t)
{
while(x <= n)
{
Q[x] += t;
x += lowbit(x);
}
}
inline double query(int x)
{
double ret = 0;
while(x)
{
ret += Q[x];
x -= lowbit(x);
}
return ret;
}
int main()
{
scanf("%d", &n);
for (int i=1; i<n; i++)
{
int u, v;double w;
scanf("%d%d%lf", &u, &v, &w);
add(u, v, w);add(v, u, w);
}
root[1] = 1;
q.push(1);
while(!q.empty())
{
int k = q.front(); q.pop();
dfs(k, 1.0);
}
scanf("%d", &m);
for (int i=1; i<=m; i++)
{
int A;
scanf("%d", &A);
if (A == 1)
{
int x; double y;
scanf("%d%lf", &x, &y);
y /= W[x];
add(l[x], y);
add(r[x]+1, -y);
}
else
{
int x;
scanf("%d", &x);
printf("%.8lf\n", query(cnt[x]) * W[x]);
}
}
return 0;
}