[Luogu 3787] 冰精冻西瓜

Description

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

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

琪露诺会做出两种动作:

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

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

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

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

Input

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

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

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

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

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

第一个数只能是1或9。

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

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

Output

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

Solution

对于那些边权为0的边，显然只有从这条边下面出发的冷气才能对这棵子树有贡献。所以不妨将所有边权为0的边看作不存在的边，将这棵树划分成几个内部边权都不为0的联通块，易证，每个联通块都是一棵树。

然后dfs一遍求出每棵树内每个点到根节点的边权之积，也就是说，求出如果有一个寒冷程度为1的冷气从根节点出发，到达每个节点的寒冷程度贡献要求出来为 dis。

然后就可以线段树做了。

ps:因为dis是从根节点出发到当前这个点的乘积，所以修改的时候要用读入的y除以当前的dis才是真正要改的值。

编辑器换了字体心情都好起来了

Code

#include<cstdio>

#include<cctype>

#include<vector>

#define N 100005

#define db double

#define min(A,B) ((A)<(B)?(A):(B))

#define max(A,B) ((A)>(B)?(A):(B))

#define swap(A,B) ((A)^=(B)^=(A)^=(B))

db dis[N];

int n,cnt,m;

db ch[N<<2];

std::vector<int> son;

int dfn[N],tot,sze[N];

db sum[N<<2],lazy[N<<2];

int head[N],vis[N],fs[N];

struct Edge{

	int to,nxt;

	db dis;

}edge[N<<1];

void add(int x,int y,db z){

	edge[++cnt].to=y;

	edge[cnt].nxt=head[x];

	edge[cnt].dis=z;

	head[x]=cnt;

}

int getint(){

	int x=0,f=0;char ch=getchar();

	while(!isdigit(ch)) f|=ch=='-',ch=getchar();

	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return x;

}

void dfs2(int now){

	sze[now]=1;dfn[now]=++tot;fs[tot]=now;

	for(int i=head[now];i;i=edge[i].nxt){

		int to=edge[i].to;

		if(sze[to]) continue;

		if(edge[i].dis==0){

			son.push_back(to);

			continue;

		}

		dis[to]=edge[i].dis*dis[now];

		dfs2(to);

		sze[now]+=sze[to];

	}

}

void build(int cur,int l,int r){

	if(l==r){

		ch[cur]=dis[fs[l]];

		return;

	}

	int mid=l+r>>1;

	build(cur<<1,l,mid);

	build(cur<<1|1,mid+1,r);

	ch[cur]=ch[cur<<1]+ch[cur<<1|1];

}

void pushdown(int cur){

	if(lazy[cur]==0) return;

	sum[cur<<1]+=lazy[cur]*ch[cur<<1];

	sum[cur<<1|1]+=lazy[cur]*ch[cur<<1|1];

	lazy[cur<<1]+=lazy[cur];

	lazy[cur<<1|1]+=lazy[cur];

	lazy[cur]=0;

}

void modify(int cur,int l,int r,int ql,int qr,db c){

	if(ql<=l and r<=qr){

		sum[cur]+=c*ch[cur];

		lazy[cur]+=c;

		return;

	}

	int mid=l+r>>1;

	pushdown(cur);

	if(ql<=mid)

		modify(cur<<1,l,mid,ql,qr,c);

	if(mid<qr)

		modify(cur<<1|1,mid+1,r,ql,qr,c);

	sum[cur]=sum[cur<<1]+sum[cur<<1|1];

}

db query(int cur,int l,int r,int ql,int qr){

	if(ql<=l and r<=qr)

		return sum[cur];

	pushdown(cur);

	int mid=l+r>>1;

	if(ql<=mid)

		return query(cur<<1,l,mid,ql,qr);

	else

		return query(cur<<1|1,mid+1,r,ql,qr);

}

signed main(){

	n=getint();

	for(int i=1;i<n;i++){

		int x=getint(),y=getint();

		db z;scanf("%lf",&z);

		add(x,y,z);add(y,x,z);

	}

	son.push_back(1);

	for(int i=0;i<son.size();i++)

		dis[son[i]]=1.0,dfs2(son[i]);

	build(1,1,n);

	m=getint();

	while(m--){

		if(getint()==1){

			int x=getint();

			db y;scanf("%lf",&y);

			modify(1,1,n,dfn[x],dfn[x]+sze[x]-1,y/dis[x]);

		} else{

			int x=getint();

			printf("%.8lf\n",query(1,1,n,dfn[x],dfn[x]));

		}

	}

	return 0;

}

巴特西