题目背景

[Luogu3787] 冰精冻西瓜-LMLPHP

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

题目描述

琪露诺是拥有操纵冷气程度的能力的妖精,一天她发现了一片西瓜地。这里有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的西瓜的寒冷程度值。

输出格式:

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

输入输出样例

输入样例#1:

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:

3.00000000
0.00000000
0.00000000
4.42856031
4.42856031
4.23333761

说明

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

“西瓜树”退化为一条链

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

[Luogu3787] 冰精冻西瓜-LMLPHP

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

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

命题人:orangebird,鸣谢oscar。


考虑如果只是从1号节点放冰, 那么它的答案就是$\large sum*pi$.

$pi$是指从根节点到$i$的$ki$的乘积。

我们把这棵树的dfs序搞出来,然后这样就变成了处理序列上的问题,然后发现无法区间处理。

但是想想,我们每次修改子树x的时候,只要整颗子树加上 $\large y / px$,然后询问的时候再乘上$pi$就可以得到答案了。


#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
#define reg register
inline int read() {
int res = ;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) res=(res<<)+(res<<)+(ch^), ch=getchar();
return res;
}
#define double long double
#define N 100005
int n, m;
struct edge {
int nxt, to;
double val;
}ed[N*];
int head[N], cnt;
inline void add(int x, int y, double z)
{
ed[++cnt] = (edge){head[x], y, z};
head[x] = cnt;
}
double p[N];
int root[N], numroot;
int f[N]; int in[N], out[N], tot; void dfs(int x, int fa)
{
in[x] = ++tot;
for (reg int i = head[x] ; i ; i = ed[i].nxt)
{
int to = ed[i].to;
if (to == fa) continue;
if (fabs(ed[i].val) <= 1e-) {
root[++numroot] = to;
f[numroot] = x;
continue;
}
p[to] = p[x] * ed[i].val;
dfs(to, x);
}
out[x] = tot;
} double tr[N];
inline void add(int x, double z)
{
while(x <= n) {
tr[x] += z;
x += x & -x;
}
}
inline double ask(int x)
{
double res = ;
while(x) {
res += tr[x];
x -= x & -x;
}
return res;
} int main()
{
n = read();
for (reg int i = ; i < n ; i ++)
{
int x = read(), y = read();
double z;
scanf("%Lf", &z);
add(x, y, z), add(y, x, z);
}
p[] = 1.0;
dfs(, );
for (reg int i = ; i <= numroot ; i ++)
{
p[root[i]] = 1.0;
dfs(root[i], f[i]);
}
m = read();
while(m--)
{
int opt = read();
if (opt == ) {
int x = read();
double y;scanf("%Lf", &y);
add(in[x], (double)y / (double)p[x]), add(out[x] + , - (double)y / (double)p[x]);
} else {
int x = read();
printf("%.8Lf\n", ask(in[x]) * p[x]);
}
}
return ;
}
05-27 20:28