Luogu冰精冻西瓜
2017-08-02冰精冻西瓜
题目描述
琪露诺是拥有操纵冷气程度的能力的妖精，一天她发现了一片西瓜地。这里有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的西瓜的寒冷程度值。
输出格式： 对于每个操作⑨，输出一行一个实数，表示对应西瓜的寒冷程度值。
强行树状数组 对一颗子树操作，我们可以联想到区间处理 那么，就要对树重新编码，让一颗子树映射到一段连续的区间上 遇到一个边权为0的边，那么冷气会在这里中断，所以要从这里断开，新建一颗树 这样，我们就得到了森林 如果所有的冷气都从某颗树的树根释放，那么只要记录一下[从该点到树根的边权积,用k表示]，就能够方便的求出某棵子树的任意一点的寒冷值：区间求和，求出该点的根释放了多少冷气，再乘上去就好了 所以对于不是从根释放的冷气，我们仍然可以强制让他从根释放 这样，如果直接进行上边的操作，会多乘上一部分，该部分是从根到原本释放点的值 所以，对x增加it，可以认为是对根增加 it/k[x] 然后为了求和方便，我们对于某颗树增加的时候，可以在这棵树的控制范围以外的地方加上负的权值，这样就省下了一个减去区间外的值的操作（虽然也并没有方便多少就是了） 代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#define N 200000
#define ld long double
#define R register
#define M N*4
const ld LL=1e-8;
using namespace std;
ld w[M],k[N],f[N];
int root[N],cnt[N],knt,n,m,e,to[M],next[M],head[N];
int l[N],r[N];
queue<int> q;
void buid(int u,int v,ld ll)
{
next[++e]=head[u],head[u]=e;
to[e]=v;w[e]=ll;
}
void dfs(int now,ld t)
{
k[now]=t;
cnt[now]=++knt;
l[now]=knt;
for(int i=head[now];i;i=next[i])
{
int j=to[i];
if(root[j]) continue;
if(!cnt[j]&&!w[i]) {root[j]=1;q.push(j);continue;}
if(!cnt[j])
{
cnt[j]=1;
dfs(j,t*w[i]);
}
}
r[now]=knt;
}
int low(int now)
{
return now&(-now);
}
ld ask(int now)
{
ld re=0;
for(int i=now;i;i-=low(i))
{
re+=f[i];
}
return re;
}
void add(int now,ld it)
{
for(int i=now;i<=n;i+=low(i))
{
f[i]+=it;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;++i)
{
R int u,v;
R ld ll;
scanf("%d%d%Lf",&u,&v,&ll);
buid(u,v,ll);
buid(v,u,ll);
}
root[1]=1;
q.push(1);
while(!q.empty())
{
int now=q.front();q.pop();
// cout<<"root "<<now<<endl;
dfs(now,1.0);
}
// for(int i=1;i<=n;++i) cout<<k[i]<<endl;
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
int fl,u;
scanf("%d%d",&fl,&u);
if(fl==9)
{
ld ans=ask(cnt[u])*k[u];
printf("%.8Lf\n",ans);
}
else
{
ld it;
scanf("%Lf",&it);
it/=k[u];
add(l[u],it);
add(r[u]+1,-it);
}
}
return 0;
}