#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define f first
#define s second
#define pii pair <int,int>
#define en '\n'
void boos() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int N = 2e5 + 100;
const int M = 4e5 + 100;
ll L;
ll binpow(ll a,ll b) {
ll ans = 1,k = a;
while(b) {
if(b % 2ll)ans *= k;
ans %= L;
k *= k;
k %= L;
b /= 2ll;
}
return ans;
}
vector <int> g[N];
pii c[M];
ll a[N];
ll dop[N][42];
bool ban[N];
int pr[N],h[N],tin[N],tout[N],Tima,up[N][22],n,sz[N];
pii mxsz[N];
map <int,ll> canc[N][42];
void dfs_build1(int v,int p) {
for(int i = 1;i <= 20;i++)up[v][i] = up[up[v][i - 1]][i - 1];
tin[v] = ++Tima;
for(auto to : g[v]) {
if(to == p)continue;
up[to][0] = v;
h[to] = h[v] + 1;
dfs_build1(to,v);
}
tout[v] = Tima;
}
bool upper(int v,int u) {
return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int getD(int x,int y) {
if(upper(x,y))return h[y] - h[x];
if(upper(y,x))return h[x] - h[y];
int val = h[x] + h[y];
for(int i = 20;i >= 0;i--) {
if(!upper(up[x][i],y)) {
x = up[x][i];
}
}
x = up[x][0];
return val - 2 * h[x];
}
void dfs_rebuild(int v,int p) {
sz[v] = 1;
mxsz[v] = mp(-1,-1);
for(auto to : g[v]) {
if(to == p || ban[to])continue;
dfs_rebuild(to,v);
sz[v] += sz[to];
mxsz[v] = max(mxsz[v],mp(sz[to],to));
}
}
int dfs_build(int v,int p) {
dfs_rebuild(v,p);
int bilo = sz[v];
while(mxsz[v].f * 2 > sz[v]) {
v = mxsz[v].s;
}
ban[v] = 1;
for(auto to : g[v]) {
if(ban[to])continue;
pr[dfs_build(to,v)] = v;
}
return v;
}
void upd(int x,int dist,ll w) {
int v = x,bilo = -1;
while(v != -1) {
int dd = dist - getD(x,v);
//cout << v << " " << bilo << " " << dd << en;
if(dd >= 0) {
dop[v][dd]++;
if(bilo != -1)canc[v][dd][bilo]++;
}
bilo = v;
v = pr[v];
}
}
ll get(int x) {
int v = x;
int bilo = -1;
ll tek = 0;
while(v != -1) {
int dd = getD(x,v);
for(int j = dd;j <= 40;j++) {
tek += dop[v][j];
if(bilo != -1)tek -= canc[v][j][bilo];
}
bilo = v;
v = pr[v];
}
return (binpow(2ll,tek) * a[x]) % L;
}
/*
*/
void solve() {
cin >> n >> L;
for(int i = 1;i <= n;i++) {
pr[i] = -1;
for(int j = 0;j <= 40;j++) {
dop[i][j] = 0;
canc[i][j].clear();
}
}
for(int i = 1;i < n;i++) {
int x,y;
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
for(int i = 1;i <= n;i++)cin >> a[i];
int q;
cin >> q;
dfs_build1(1,-1);
dfs_build(1,-1);
//cout << "OK" << endl;
for(int i = 1;i <= q;i++) {
int typ;
cin >> typ;
if(typ == 1) {
int x,dist;
ll w;
cin >> x >> dist >> w;
upd(x,dist,w);
}else {
int x;
cin >> x;
cout << get(x) << en;
}
}
}
int main() {
boos();
int ttt;
ttt = 1;
while(ttt--) {
solve();
}
}
Compilation message
sprinkler.cpp: In function 'int dfs_build(int, int)':
sprinkler.cpp:75:6: warning: unused variable 'bilo' [-Wunused-variable]
75 | int bilo = sz[v];
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
310 ms |
399880 KB |
Output is correct |
| 2 |
Incorrect |
195 ms |
399808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
399740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
399740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
217 ms |
399820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
399784 KB |
Output is correct |
| 2 |
Execution timed out |
4096 ms |
516416 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
310 ms |
399880 KB |
Output is correct |
| 2 |
Incorrect |
195 ms |
399808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
