Submission #1274407

#TimeUsernameProblemLanguageResultExecution timeMemory
1274407altern23Sprinkler (JOI22_sprinkler)C++20
0 / 100
689 ms90560 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 2e5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

void add(ll &a, ll b) { a = (a + b) % MOD; }
void sub(ll &a, ll b) { a = (a - b + MOD) % MOD; }
void mul(ll &a, ll b) { a = a * b % MOD; }

ll up[MAXN + 5], H[MAXN + 5];
ll dp[MAXN + 5][45];

vector<ll> adj[MAXN + 5];

void dfs(ll idx, ll par){
	up[idx] = par;
	for(auto i : adj[idx]){
		if(i != par) dfs(i, idx);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N, L; cin >> N >> L;
		for(int i = 2; i <= N; i++){
			ll u, v; cin >> u >> v;
			adj[u].push_back(v), adj[v].push_back(u);
		}
		
		dfs(1, 0);
		
		for(int i = 1; i <= N; i++){
			cin >> H[i];
			for(int j = 0; j <= 40; j++) dp[i][j] = 1LL;
		}
		
		ll Q; cin >> Q;
		for(int i = 1; i <= Q; i++){
			ll t; cin >> t;
			if(t == 1){
				ll idx, D, val; cin >> idx >> D >> val;
				for(;idx && D >= 0;){
					dp[idx][D] = dp[idx][D] * val % L;
					D--;
					idx = up[idx];
				}
			}
			else{
				ll idx; cin >> idx;
				ll ans = H[idx];
				for(int dep = 0; dep <= 40 && idx; dep++, idx = up[idx]){
					if(idx == 1){
						for(int j = dep; j <= 40; j++) ans = ans * dp[idx][j] % L;
						break;
					}
					ans = ans * dp[idx][dep] % L;
					ans = ans * dp[idx][dep + 1] % L;
				}
				
				cout << ans << "\n";
			}
		}
	}
}	

/*

*/
#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...