列表

详情

NC202310. A Simple Problem On A Tree

描述

We have met so many problems on the tree, so today we will have a simple problem on a tree.
You are given a tree (an acyclic undirected connected graph) with nodes. The tree nodes are numbered from to . Each node has a weight . We will have four kinds of operations on it and you should solve them efficiently. Wish you have fun!

输入描述

The first line of the input gives the number of test case,  ().  test cases follow.
For each case, the first line contains only one integer .() The next  lines each contains two integers ,  which means there is an edge between them. It also means we will give you one tree initially. 
The next line will contains  integers which means the initial weight  of each node. ()
The next line will contains an integer . () The next  lines will start with an integer 1, 2, 3 or 4 means the kind of this operation.
1.Given three integers , , , for the ,  and all nodes between the path from  to  inclusive, you should update their weight to . (, )
2.Given three integers , , ,  for the ,  and all nodes between the path from  to  inclusive, you should increase their weight by . (, )
3. Given three integers , , , for the ,  and all nodes between the path from  to  inclusive, you should multiply their weight by . (, )
4.Given two integers , , you should check the node weights on the path between  and , and you should output cubic sum of them. It means, output ,  is node on the path from  to  (inclusive  and ). ()

输出描述

For each test case, output one line containing ``Case #x:'', where x is the test case number (starting from 1).
For operation 4, output a single integer in one line representing the result. The result could be huge, print it module 1,000,000,007.

示例1

输入: 

1
5
2 1
1 3
5 3
4 3
1 2 3 4 5
6
4 2 4
1 5 4 2
2 2 4 3
3 2 3 4
4 5 4
4 2 4

输出: 

Case #1:
100
8133
20221

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 2325ms, 内存消耗: 30588K, 提交时间: 2020-12-09 17:53:07 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define lx x<<1
#define rx x<<1|1
int fa[N],son[N],top[N],sz[N],dfn[N],rk[N],dep[N],w[N];
vector<int>e[N];
int T,n,Q,tim;
struct node{
	int l,r;
	ll ad,mu,s1,s2,s3;
}a[N<<2]; 
void dfs(int u,int f){
	sz[u]=1,fa[u]=f,dep[u]=dep[f]+1,son[u]=0;
	for(int v:e[u]){
		if(v==f) continue;
		dfs(v,u),sz[u]+=sz[v];
		if(sz[son[u]]<sz[v]) son[u]=v;
	}
}
void dfs1(int u,int t){
	top[u]=t,dfn[u]=++tim,rk[tim]=u;
	if(son[u]) dfs1(son[u],t);
	for(int v:e[u]){
		if(v==fa[u]||v==son[u]) continue;
		dfs1(v,v);
	}
}
void re(int x){
	a[x].s1=(a[lx].s1+a[rx].s1)%mod;
	a[x].s2=(a[lx].s2+a[rx].s2)%mod;
	a[x].s3=(a[lx].s3+a[rx].s3)%mod; 
}
void bud(int x,int l,int r){
	a[x].l=l,a[x].r=r,a[x].mu=1,a[x].ad=0;
	if(l==r){
		ll y=w[rk[l]];
		a[x].s1=y%mod;
		a[x].s2=a[x].s1*y%mod;
		a[x].s3=a[x].s2*y%mod;return;
	}int mid=l+r>>1;
	bud(lx,l,mid),bud(rx,mid+1,r),re(x);
}
void phd1(int x,int s,ll c){
	ll mu=a[x].mu,ad=a[x].ad;
	a[s].mu=a[s].mu*mu%mod,a[s].ad=a[s].ad*mu%mod,a[s].ad=(a[s].ad+ad)%mod;
	a[s].s1=a[s].s1*mu%mod,a[s].s2=a[s].s2*mu%mod*mu%mod,a[s].s3=a[s].s3*mu%mod*mu%mod*mu%mod;
	a[s].s3=(a[s].s3+3*ad%mod*a[s].s2%mod+3*ad%mod*ad%mod*a[s].s1%mod+c*ad%mod*ad%mod*ad%mod)%mod;
	a[s].s2=(a[s].s2+2*ad%mod*a[s].s1%mod+c*ad%mod*ad%mod)%mod;
	a[s].s1=(a[s].s1+c*ad%mod)%mod;
}
void phd(int x){
	phd1(x,lx,a[lx].r-a[lx].l+1);
	phd1(x,rx,a[rx].r-a[rx].l+1);
	a[x].mu=1,a[x].ad=0;
}
void upd(int x,int l,int r,ll mu,ll ad){
	if(l<=a[x].l&&r>=a[x].r){
		  a[0].mu=mu,a[0].ad=ad;
		  phd1(0,x,a[x].r-a[x].l+1);
		return;
	}
	int mid=a[x].l+a[x].r>>1;
	phd(x);
	if(l<=mid) upd(lx,l,r,mu,ad);
	if(r>mid) upd(rx,l,r,mu,ad); 
	re(x);
}
ll que(int x,int l,int r){
	if(a[x].l>=l&&a[x].r<=r) return a[x].s3;
	ll ans=0,mid=a[x].l+a[x].r>>1;
	phd(x);
	if(l<=mid) ans+=que(lx,l,r);
	if(r>mid) ans+=que(rx,l,r);
	return ans%mod;
}
void UPD(int u,int v,ll m,ll a){
	while(top[u] != top[v]){
 
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        upd(1,dfn[top[u]],dfn[u], m, a);
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    upd(1,dfn[v],dfn[u],m,a);
}
ll QUE(int u, int v){
 
    ll ans = 0;
    while(top[u] != top[v]){
 
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        ans+=que(1,dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    ans += que(1, dfn[v], dfn[u]);
    return ans % mod;
}
int main(){
	scanf("%d",&T);for(int k=1;k<=T;k++){
		scanf("%d",&n);for(int i=1,u,v;i<n;i++)
			scanf("%d%d",&u,&v),e[u].pb(v),e[v].pb(u);
		for(int i=1;i<=n;i++) scanf("%d",&w[i]);scanf("%d",&Q);tim=0;
		dfs(1,0),dfs1(1,1);
		bud(1,1,n);
		printf("Case #%d:\n",k);
		while(Q--){int op,u,v,w;scanf("%d%d%d",&op,&u,&v);
		if(op==1)	scanf("%d",&w),UPD(u,v,0,w);
		else if(op==2)   scanf("%d",&w),UPD(u,v,1,w);
		else if(op==3)	scanf("%d",&w),UPD(u,v,w,0);
		else 		printf("%lld\n",QUE(u,v));
		}for(int i=1;i<=n;i++) e[i].clear();
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 10110ms, 内存消耗: 36448K, 提交时间: 2020-07-16 17:34:51 

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 1e5 + 10;
int top[N];
int in[N];
int out[N];
int sz[N];
int depth[N];
int fa[N];
vector<int> v[N];
int cnt = 0;
int a[N];
int b[N];
int dfssz(int x, int fa = 0)
{
	::fa[x] = fa;
	depth[x] = depth[fa] + 1;
	sz[x] = 0;
	int ret = 1;
	for (int i = 0; i < v[x].size(); i++)
	{
		int y = v[x][i];
		if (y == fa) continue;
		ret += dfssz(y, x);
	}
	sort(v[x].begin(), v[x].end(), [](int x, int y)->bool
		{
			return sz[x] > sz[y];
		});
	return sz[x] = ret;
}
void dfshld(int x, int fa = 0)
{
	in[x] = ++cnt;
	for (int i = 0; i < v[x].size(); i++)
	{
		int y = v[x][i];
		if (v[x][i] == fa) continue;
		top[y] = (i == 0 ? top[x] : y);
		dfshld(y, x);
	}
	out[x] = cnt;
}
void query(int x, int y, vector<pair<int, int> >& vp)
{
	while (top[x] != top[y])
	{
		if (depth[top[x]] < depth[top[y]]) swap(x, y);
		vp.push_back(make_pair(in[top[x]], in[x]));
		x = fa[top[x]];
	}
	if (in[x] > in[y]) swap(x, y);
	vp.push_back(make_pair(in[x], in[y]));
}
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int ncase;
	cin >> ncase;
	int ks = 1;
	while (ncase--)
	{
		cout << "Case #" << ks++ << ":\n";
		int n, q;
		cnt = 0;
		top[1] = 1;
		cin >> n;

		for (int i = 1; i <= n; i++) v[i].clear();
		for (int i = 1; i < n; i++)
		{
			int x, y;
			cin >> x >> y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		for (int i = 1; i <= n; i++)
		{
			cin >> b[i];
		}
		dfssz(1);
		dfshld(1);
		for (int i = 1; i <= n; i++)
		{
			a[in[i]] = b[i];
		}
		cin >> q;
		while (q--)
		{
			int op, x, y, w;
			cin >> op >> x >> y;
			vector<pair<int, int>> vp;
			query(x, y, vp);
			if (op <= 3) cin >> w;
			if (op == 1)
			{
				for (auto& p : vp)
				{
					int l, r;
					tie(l, r) = p;
					for (int i = l; i <= r; i++)
					{
						a[i] = w;
					}
				}
				continue;
			}
			if (op == 2)
			{
				for (auto& p : vp)
				{
					int l, r;
					tie(l, r) = p;
					for (int i = l; i <= r; i++)
					{
						a[i] = (a[i] + w) % INF;
					}
				}
				continue;
			}
			if (op == 3)
			{
				for (auto& p : vp)
				{
					int l, r;
					tie(l, r) = p;
					for (int i = l; i <= r; i++)
					{
						a[i] = (1LL * a[i] * w) % INF;
					}
				}
				continue;
			}
			if (op == 4)
			{
				__int128 ans = 0;
				for (auto& p : vp)
				{
					int l, r;
					tie(l, r) = p;
					for (int i = l; i <= r; i++)
					{
						__int128 x = a[i];
						ans += x * x * x;
					}
				}
				long long res = ans % INF;
				cout << res << '\n';
			}
		}
	}
	return 0;
}

上一题

© 2024 nowcoder.com