Submission #1130877

#TimeUsernameProblemLanguageResultExecution timeMemory
1130877nguyenkhangninh99Sprinkler (JOI22_sprinkler)C++20
21 / 100
2029 ms185208 KiB

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn = 2e5 + 69;

vector<int> g[maxn];

int mod;

int h[maxn];
int depth[maxn], par[maxn];
int f[maxn][100];

void dfs(int u, int pre){
	depth[u] = depth[pre] + 1;
	par[u] = pre;
	for(int v: g[u]){
		if(v == pre) continue;
		dfs(v, u);
	}
}
void solve(){
	int n; cin >> n >> mod;

	for(int i = 1; i <= n - 1; i++){
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	for(int i = 1; i <= n; i++) cin >> h[i];

	dfs(1, 0);
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 100; j++) f[i][j] = 1;
	}

	int q; cin >> q;

	while(q--){
		int type; cin >> type;
		if(type == 1){
			int u, d, w; cin >> u >> d >> w;
			if(d == 0) (f[u][d] *= w) %= mod;
			else{
				int temp = d;
				for(int i = 0; i + 2 <= temp; i++){
					(f[u][d] *= w) %= mod;
					(f[u][d - 1] *= w) %= mod;
					///cout << u << " " << d << "\n";
					d -= 1;
					u = par[u];
					if(!u) break;
				}

				if(!u){
					for(int j = 0; j <= d; j++) (f[1][j] *= w) %= mod;
				}
				if(u){
					(f[u][0] *= w) %= mod;
					(f[u][1] *= w) %= mod;
					(f[par[u]][0] *= w) %= mod;
				}
			}
		}

		else{
			int u; cin >> u;
			int res = h[u];
        	for (int d = 0; u && d <= 40; d++, u = par[u]){
				res = (res * f[u][d]) % mod;
				//cout << u << " " <<d << " " << f[u][d] << "\n";
			}
        	cout << res << "\n";
		}
		
	}
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...