题意

分析

考场暴力50分。
考虑bfs序，一个点的儿子节点的bfs序一定连续，所以对bfs序建线段树，努力打一下就行了。
时间复杂度\(O(n \log n + m \log n)\)
#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#define rg register

#define co const

#define il inline

#pragma GCC optimize ("O0")

using namespace std;

template<class T> inline T read(T&x)

{

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

const int MAXN=2e5+7;

struct Edge

{

	int nx,to;

}E[MAXN<<1];

int head[MAXN],ecnt;

il void addedge(rg co int&x,rg co int&y)

{

	E[++ecnt].to=y;

	E[ecnt].nx=head[x],head[x]=ecnt;

}

const int mod=1e9+7;

struct node

{

	int sumv;

	il node(rg co int&s=0):sumv(s){}

	il node operator+(rg const node&rhs)const

	{

		return node((sumv + rhs.sumv) % mod);

	}

};

int ql,qr,v;

struct SegTree

{

	node data[MAXN<<2];

	int addv[MAXN<<2],mulv[MAXN<<2];

#define lson (now<<1)

#define rson (now<<1|1)

	il void build(rg int now,rg int l,rg int r)

	{

		addv[now]=0,mulv[now]=1;

		if(l==r)

		{

			data[now].sumv=0;

			return;

		}

		rg int mid=(l+r)>>1;

		build(lson,l,mid);

		build(rson,mid+1,r);

		data[now]=data[lson]+data[rson];

	}

	il void pushdown(rg int now,rg int l,rg int r)

	{

		if(mulv[now]!=1)

		{

			data[lson].sumv = (ll) data[lson].sumv * mulv[now] % mod,

			addv[lson] = (ll) addv[lson] * mulv[now] % mod;

			mulv[lson] = (ll) mulv[lson] * mulv[now] % mod;

			data[rson].sumv = (ll) data[rson].sumv * mulv[now] % mod,

			addv[rson] = (ll) addv[rson] * mulv[now] % mod;

			mulv[rson] = (ll) mulv[rson] * mulv[now] % mod;

			mulv[now] = 1;

		}

		if(addv[now])

		{

			rg int mid=(l+r)>>1;

			(data[lson].sumv += (ll) (mid - l + 1) * addv[now] % mod ) %= mod,

			(addv[lson] += addv[now]) %= mod;

			(data[rson].sumv += (ll) (r - mid) * addv[now] % mod) %= mod,

			(addv[rson] += addv[now]) %= mod;

			addv[now]=0;

		}

	}

	il node query(rg int now,rg int l,rg int r)

	{

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

		{

			return data[now];

		}

		pushdown(now,l,r);

		rg int mid=(l+r)>>1;

		if(qr<=mid)

			return query(lson,l,mid);

		if(ql>=mid+1)

			return query(rson,mid+1,r);

		return query(lson,l,mid)+query(rson,mid+1,r);

	}

	il void mul(rg int now,rg int l,rg int r)

	{

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

		{

			data[now].sumv = (ll)data[now].sumv * v % mod,

			addv[now] = (ll)addv[now] * v % mod,

			mulv[now] = (ll)mulv[now] * v % mod;

			return;

		}

		pushdown(now,l,r);

		rg int mid=(l+r)>>1;

		if(ql<=mid)

			mul(lson,l,mid);

		if(qr>=mid+1)

			mul(rson,mid+1,r);

		data[now]=data[lson]+data[rson];

	}

	il void add(rg int now,rg int l,rg int r)

	{

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

		{

			(data[now].sumv += (ll)(r - l + 1) * v % mod) %= mod,

			(addv[now] += v) %= mod;

			return;

		}

		pushdown(now,l,r);

		rg int mid=(l+r)>>1;

		if(ql<=mid)

			add(lson,l,mid);

		if(qr>=mid+1)

			add(rson,mid+1,r);

		data[now]=data[lson]+data[rson];

	}

}T;

int fa[MAXN],s1[MAXN],s2[MAXN];

il void dfs(rg co int&x,rg co int&f)

{

	fa[x]=f;

	for(rg int i=head[x];i;i=E[i].nx)

	{

		rg int y=E[i].to;

		if(y==f)

			continue;

		if(!s1[x]) // edit 1:cannot add fa

			s1[x]=y;

		s2[x]=y;

		dfs(y,x);

	}

}

int bfn[MAXN],clk;

il void bfs()

{

	rg queue<int>Q;

	Q.push(1);

	while(!Q.empty())

	{

		rg int x=Q.front();

		Q.pop();

		bfn[x]=++clk;

		for(rg int i=head[x];i;i=E[i].nx)

		{

			rg int y=E[i].to;

			if(y==fa[x])

				continue;

			Q.push(y);

		}

	}

}

int main()

{

  freopen("ruby.in","r",stdin);

  freopen("ruby.out","w",stdout);

	rg int n,m;

	read(n);read(m);

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

	{

		rg int x,y;

		read(x);read(y);

		addedge(x,y);

		addedge(y,x);

	}

	dfs(1,0);

	bfs();

	T.build(1,1,n);

	while(m--)

	{

		rg int x,k,b;

		read(x);read(k);read(b);

		rg int ans=0;

		if(bfn[fa[x]]) // edit 1:fa[root]=NULL

		{

			ql=qr=bfn[fa[x]];

			v=k;

			T.mul(1,1,n);

			v=b;

			T.add(1,1,n);

			(ans += T.query(1,1,n).sumv) %= mod;

		}

		ql=qr=bfn[x];

		v=k;

		T.mul(1,1,n);

		v=b;

		T.add(1,1,n);

		(ans += T.query(1,1,n).sumv) %= mod;

		if(bfn[s1[x]]) // edit 2:leaf has no son

		{

			ql=bfn[s1[x]],qr=bfn[s2[x]];

			v=k;

			T.mul(1,1,n);

			v=b;

			T.add(1,1,n);

			(ans += T.query(1,1,n).sumv) %= mod;

		}

		printf("%d\n",ans);

	}

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}
Hint

第一次打bfs序的题，有些细节需要注意。
一个点可能没有父节点或没有子节点，需要特判。
dfs的首尾子节点的赋值注意不要赋值成fa了。
巴特西

test20181016 B君的第二题

题意

分析

Hint

最新文章

热门文章
