线段树巨大常数T飞求救

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
typedef long long ll;
int f[maxn];
ll lp[maxn],rp[maxn],a[maxn],ans[maxn];
vector<int>e[maxn];
ll H[maxn];
map<ll,int>mp;
struct line
{
	ll l,r;
}p[maxn];
struct que
{
	ll m,ans;
	int id;
	bool operator < (const que yy)
	{
		return m<yy.m;
	}
}qu[maxn];
void dfs(int x,ll l,ll r,ll s)
{
	p[x].l=l;p[x].r=r;s+=a[x];
	for(int i=0;i<e[x].size();i++)
	{
		if(e[x][i]==f[x])
			continue;
		dfs(e[x][i],max(lp[e[x][i]],l+s)-s,min(rp[e[x][i]],r+s)-s,s);
	}
	return;
}
struct node
{
	int l,r;
	ll sum,lad;
}t[maxn<<2];
int build(int l,int r,int x)
{
	t[x].l=l,t[x].r=r;
	if(l==r)
	{
		t[x].sum=0;
		return 0;
	}
	int mid=(l+r)/2;
	t[x].sum+=build(l,mid,x*2)+build(mid+1,r,x*2+1);
	return t[x].sum;
}
void pushdown(int x)
{
	if(t[x].lad==0)
		return;
	t[x*2].lad+=t[x].lad;
	t[x*2+1].lad+=t[x].lad;
	t[x*2].sum+=1ll*t[x].lad*(t[x*2].r-t[x*2].l+1);
	t[x*2+1].sum+=1ll*t[x].lad*(t[x*2+1].r-t[x*2+1].l+1);
	t[x].lad=0;
	return;
}
void add(int l,int r,ll k,int x)
{
	if(l<=t[x].l&&t[x].r<=r)
	{
		t[x].sum+=1ll*k*(t[x].r-t[x].l+1);
		t[x].lad+=k;
		return;
	}
	pushdown(x);
	int mid=(t[x].l+t[x].r)/2;
	if(mid>=l)
		add(l,r,k,x*2);
	if(mid+1<=r)
		add(l,r,k,x*2+1);
	t[x].sum=t[x*2].sum+t[x*2+1].sum;
	return;
}
ll query(int l,int r,int x)
{
	if(l<=t[x].l&&t[x].r<=r)
		return t[x].sum;
	pushdown(x);
	int mid=(t[x].l+t[x].r)/2;
	ll ans=0;
	if(mid>=l)
		ans+=query(l,r,x*2);
	if(mid+1<=r)
		ans+=query(l,r,x*2+1);
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	int n,q;
	cin>>n>>q;
	for(int i=2;i<=n;i++)
	{
		cin>>f[i]>>lp[i]>>rp[i];
		e[i].push_back(f[i]);
		e[f[i]].push_back(i);
	}
	for(int i=1;i<=n;i++)
	{
		char op;
		cin>>op>>a[i];
		if(op=='-')
			a[i]=-a[i];
	}
	for(int i=1;i<=q;i++)
	{
		cin>>qu[i].m;
		qu[i].id=i;
	}
	sort(qu+1,qu+q+1);
	dfs(1,qu[1].m,qu[q].m,0);
	for(int i=1;i<=n;i++)
		H[2*i-1]=p[i].l,H[2*i]=p[i].r;
	for(int i=1;i<=q;i++)
		H[2*n+i]=qu[i].m;
	sort(H+1,H+2*n+q+1);
	int tot=unique(H+1,H+2*n+1+q) - (H+1);
	build(1,tot,1);
	for(int i=1;i<=tot;i++)
		mp[H[i]]=i;
	for(int i=1;i<=n;i++)
		p[i].l=mp[p[i].l],p[i].r=mp[p[i].r];
	for(int i=1;i<=q;i++)
		qu[i].m=mp[qu[i].m];
	for(int i=1;i<=n;i++)
		add(p[i].l,p[i].r,1,1);
	for(int i=1;i<=q;i++)
		qu[i].ans=query(qu[i].m,qu[i].m,1);
	for(int i=1;i<=q;i++)
		ans[qu[i].id]=qu[i].ans;
	for(int i=1;i<=q;i++)
		cout<<ans[i]<<endl;
	return 0;
}