#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e5 + 11;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;
mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());
ll n, L, q;
vector<ll> g[N];
ll sz[N];
ll h[N];
int lay[N];
ll dist[N][20];
ll cp[N];// centroid predok
bool del[N];
void dfs(ll v, ll p) {
sz[v] = 1;
for(auto u : g[v]) {
if(p == u || del[u])continue;
dfs(u, v);
sz[v] += sz[u];
}
}
void bdfs(ll v, ll p, ll k) {
cp[v] = k;
if(p == k)dist[v][lay[k]] = 1;
else dist[v][lay[k]] = dist[p][lay[k]] + 1;
for(auto u : g[v]) {
if(u == p || del[u])continue;
bdfs(u, v, k);
}
}
int fnd(int v) {
int p = 0;
int siz = sz[v];
while(p != v) {
int c = v;
for(auto u : g[c]) {
if(u != p && !del[u] && sz[u] * 2ll > siz) {
v = u;
break;
}
}
p = c;
}
return v;
}
void build(ll v, ll layer = 0) {
dfs(v, 0);
v = fnd(v);
del[v] = 1;
lay[v] = layer;
for(auto u : g[v]) {
if(!del[u])
bdfs(u, v, v);
}
for(auto u : g[v]) {
if(!del[u]) {
build(u, layer + 1);
}
}
}
int stp[N][41];
int per[N][41];
int als1[N], als2[N];
void add1(ll v, ll z) {
als1[v]++;
for(int j = z; j <= 40; j |= (j + 1))
stp[v][j]++;
}
void add2(ll v, ll z) {
als2[v]++;
for(int j = z; j <= 40; j |= (j + 1))
per[v][j]++;
}
ll get1(ll v, ll z) {
if(z >= 40)return als1[v];
ll sum = 0;
for(int j = z; j >= 0; j = (j & (j + 1)) - 1)
sum = sum + stp[v][j];
return sum;
}
ll get2(ll v, ll z) {
if(z >= 40)return als2[v];
ll sum = 0;
for(int j = z; j >= 0; j = (j & (j + 1)) - 1)
sum = sum + per[v][j];
return sum;
}
void upd(ll a, ll c, ll b) {
ll dis = 0;
ll izn = a;
int cnt = 0;
add1(a, c);
while(a) {
if(cp[a] == 0)break;
cnt++;
assert(cnt <= 40);
dis = dist[izn][lay[cp[a]]];
if(c - dis >= 0) {
add1(cp[a], c - dis);
add2(a, c - dis);
}
a = cp[a];
}
}
ll getans(ll a) {
ll dis = 0;
ll izn = a;
ll ans = als1[a];
ll pr = a;
a = cp[a];
while(a) {
dis = dist[izn][lay[a]];
ll k1 = (als1[a] - get1(a, dis - 1));
ll k2 = (als2[pr] - get2(pr, dis - 1));
ans += k1 - k2;
pr = a;
a = cp[a];
}
return ans;
}
ll prec[N * 3];
int main() {
speed;
cin >> n >> L;
prec[0] = 1;
for(int i = 1; i <= 500000; i++)
prec[i] = prec[i - 1] * 2ll % L;
for(int i = 1, a, b; i < n; i++) {
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
for(int i = 1; i <= n; i++) {
cin >> h[i];
}
build(1);
cin >> q;
while(q--) {
ll t, a, b, c;
cin >> t >> a;
if(t == 1) {
cin >> b >> c;
upd(a, b, c);
} else {
ll z = getans(a);
cout << h[a] * prec[z] << "\n";
}
}
}
/*
7 10
1 2
1 3
1 4
1 5
2 6
2 7
1 1 1 1 1 1 1
8
1 6 2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8916 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
8964 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
8900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
8900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
8916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
8916 KB |
Output is correct |
| 2 |
Incorrect |
1258 ms |
133532 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8916 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
8964 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
