题目描述
琪露诺是拥有操纵冷气程度的能力的妖精,一天她发现了一片西瓜地。这里有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
说明
子任务可能出现如下的特殊性质:
“西瓜树”退化为一条链
输入数据中的实数均保留8位小数,选手的答案被判作正确当且仅当输出与标准答案误差不超过10^-7。请特别注意浮点数精度问题。
实际数据中,冷气的寒冷程度x的范围为 [-0.1,0.1]
(样例中的冷气寒冷程度的范围为[1,5])
Hint:冷气只会向释放点的子树蔓延,不会向根方向蔓延
题目说的很清楚,这里就不解释了。(再说我也解释不来)
其实,这种题目第一眼看到就是这种类型的维护来维护去的。由于本题的特殊性,我们可以获得以下几点:
1.每当有1操作时,其实相当于从根节点出发,但是那冷气的初始寒冷值是要改变的。怎么改变?设从根节点到节点x路径上的所以w的积为dec,那么寒冷值就要变为原来的dec(倍);
2.当出现w=0时,无法直接运用上述规律;
3.当w=0时,建一棵新树,使当前节点成为根节点,并与原来的树相对独立(可能有很多棵,请深入思考,怎样做到相对独立);(Important!!!)
4.由于要运用到树状数组,所以我们要将有关联的节点放到一起来——怎么办?构造入栈时刻数组in和出栈时刻数组out。节点x影响到的将会是in[x]~out[x](in[x]<=out[x]),因此,我们在Update时,应该这么做:Update(in[x],dec),Update(out[x]+1,-dec),相当于构造后缀和;同样,在Query时应该是Query(in[x]),但是,别忘了,这只是对于根节点来说的(尽管根节点不一定就得到那么多),我们还应该乘以w[x](w[x]即为从根节点到节点x路径上的所以w的积)。
根据以上几点,不难构建出代码。
代码如下:
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #define M(Ar) memset(Ar,0,sizeof Ar); using namespace std; ; int n,Q,fa[maxn],cloc,incl[maxn],outcl[maxn]; bool vis[maxn]; double w[maxn],cold[maxn]; vector <int> G[maxn]; vector <double> A[maxn]; queue <int> q; inline int read(){ ; char ch=getchar(); ') ch=getchar(); +ch-',ch=getchar(); return x; } inline void add(int x,int y,double z){ G[x].push_back(y),A[x].push_back(z); G[y].push_back(x),A[y].push_back(z); } inline void DFS(int x){ vis[x]=,incl[x]=++cloc; int sz=G[x].size(); ; i<sz; i++) ) w[G[x][i]]=1.00000000*w[x]*A[x][i],DFS(G[x][i]); else if (!vis[G[x][i]]) q.push(G[x][i]); outcl[x]=cloc; } inline void Update(int x,double z){ for (int i=x; i<=n; i+=i&(-i)) cold[i]+=z; } inline double Query(int x){ ; for (int i=x; i; i-=i&(-i)) ret+=cold[i]; return ret; } int main(){ n=read(); ; i<n; i++){ int x=read(),y=read(); double z; scanf("%lf",&z); add(x,y,z); } q.push(),cloc=,M(vis); ,DFS(q.front()),q.pop(); Q=read(),M(cold); for ( ; Q; Q--){ int op=read(); ){ int x=read(); double z; scanf("%lf",&z); double dec=z/w[x]; Update(incl[x],dec),Update(outcl[x]+,-dec); }else ){ int x=read(); printf("%.8lf\n",Query(incl[x])*w[x]); } } ; }