树剖0pts求助,悬赏5.14关注
查看原帖
树剖0pts求助,悬赏5.14关注
446327
mukari楼主2023/1/28 09:21
#include<bits/stdc++.h>
#define ll long long
#define ma 511451
#define il inline
using namespace std;
const ll inf=1e18+10;
ll read(){
	char ch=getchar();
	ll x=0,f=1;
	while('0'>ch||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>=10){
		write(x/10);
	}
	putchar(x%10+'0');
}
//--------------------------------------------
ll n,m;
//--------------------------------------------
ll head[ma],ver[ma],nxt[ma],tot=0;
double edge[ma];
void add(ll x,ll y,double z){
	ver[++tot]=y,edge[tot]=z;
	nxt[tot]=head[x],head[x]=tot;
}
void Add(ll x,ll y,double z){
	add(x,y,z),add(y,x,z);
}
//--------------------------------------------
ll top[ma],fa[ma],siz[ma],son[ma],dep[ma];
double v[ma],val[ma];
ll id[ma],cnt=0;
void dfs1(ll x){
	dep[x]=dep[fa[x]]+1;
	siz[x]=1;
	for(ll i=head[x];i;i=nxt[i]){
		ll y=ver[i];
		double z=edge[i];
		if(y==fa[x]) continue;
		fa[y]=x;
		v[y]=z;
		dfs1(y);
		siz[x]+=siz[y];
		if(!son[x]||siz[son[x]]<siz[y]) son[x]=y;
	}
}
void dfs2(ll x,ll tp){
	id[x]=++cnt;
	val[cnt]=v[x];
	top[x]=tp;
	if(!son[x]) return;
	dfs2(son[x],tp);
	for(ll i=head[x];i;i=nxt[i]){
		ll y=ver[i];
		if(y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}
//--------------------------------------------
#define ls p<<1
#define rs p<<1|1
struct seg{
	double val;
	double ab;
	double laz;
}t[ma<<2];
ll idx[ma];
void pushup(ll p){
	t[p].val=t[ls].val+t[rs].val;
	t[p].ab=t[ls].ab+t[rs].ab;
}
void down(ll p,ll l,ll r){
	if(t[p].laz){
		t[ls].laz+=t[p].laz,t[rs].laz+=t[p].laz;
		t[ls].val+=t[ls].ab*t[p].laz;
		t[rs].val+=t[rs].ab*t[p].laz;
		t[p].laz=0;
	}
}
void build(ll p,ll l,ll r){
	t[p].ab=1;
	if(l==r){
		t[p].ab=val[l];
		idx[l]=p;
		return;
	}
	ll mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(p);
}
void update(ll p,ll l,ll r,ll x,ll y,double k){
	if(l>r) return;
	if(x<=l&&r<=y){
		t[p].val+=(double)k*t[p].ab;
		t[p].laz=k;
		return;
	}
	down(p,l,r);
	ll mid=(l+r)>>1;
	if(x<=mid) update(ls,l,mid,x,y,k);
	if(y>mid) update(rs,mid+1,r,x,y,k);
	pushup(p);
}
double ask(ll p,ll l,ll r,ll x){
	if(l>r) return 0;
	if(l==r) return t[p].val;
	down(p,l,r);
	ll mid=(l+r)>>1;
	if(x<=mid) return ask(ls,l,mid,x);
	else return ask(rs,mid+1,r,x);
}
//--------------------------------------------
void tree_up(ll x,double k){
	ll pos=id[x]+siz[x]-1;
	for(ll i=id[x];i<=pos;i++){
		if(t[idx[i]].ab==0){
			pos=i;
			break;
		}
	}
	if(t[idx[id[x]]].ab==0) pos=id[x]+siz[x]-1,t[idx[id[x]]].val+=k;
	update(1,1,n,id[x],pos,k);
}
double dot_ask(ll x){
	return ask(1,1,n,id[x]);
}
//--------------------------------------------
int main(){
	freopen("debug.in","r",stdin);
	n=read();
	for(ll i=1;i<n;i++){
		ll x=read(),y=read();
		double z;
		scanf("%lf",&z);
		Add(x,y,z);
	}
	m=read();
	dfs1(1),dfs2(1,1);
	val[1]=1;
	build(1,1,n);
	while(m--){
		ll op=read();
		ll x=read();
		double k;
		if(op==1){
			scanf("%lf",&k);
			tree_up(x,k);
		}
		if(op==9){
			printf("%.8lf\n",dot_ask(x));
		}
	}
	return 0;
}

感觉树剖没问题,但是题解没有树剖,求查错

2023/1/28 09:21
加载中...