Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #include <string>
- #include <string.h>
- #include <utility>
- #include <map>
- #include <list>
- using namespace std;
- typedef pair <int, int> pii;
- typedef long long ll;
- #define pb push_back
- #define mp make_pair
- #define f first
- #define s second
- const int maxn = 5e5 + 10;
- int n, m;
- vector <int> g[maxn];
- int par[maxn];
- void set_parity(int u, int p, int x) {
- par[u] = x;
- for (int v : g[u]) {
- if (v == p) continue;
- set_parity(v, u, x ^ 1);
- }
- }
- int dep[maxn], sz[maxn], son[maxn];
- void dfs1(int u, int p) {
- dep[u] = dep[p] + 1;
- sz[u] = 1;
- son[u] = -1;
- for (int v : g[u]) {
- if (v == p) continue;
- dfs1(v, u);
- sz[u] += sz[v];
- if (sz[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
- }
- }
- int seq[maxn], num, id[maxn], top[maxn], fa[maxn];
- void dfs2(int u, int p) {
- fa[u] = p;
- seq[++num] = u;
- id[u] = num;
- if (son[u] != -1) {
- top[son[u]] = top[u];
- dfs2(son[u], u);
- }
- for (int v : g[u]) {
- if (v == p || v == son[u]) continue;
- top[v] = v;
- dfs2(v, u);
- }
- }
- ll val[maxn * 4][2], add[maxn * 4][2];
- void pushdown(int t, int l, int r, int tp) {
- int lc = t << 1, rc = t << 1 | 1, mid = (l + r) >> 1;
- add[lc][tp] += add[t][tp];
- val[lc][tp] += add[t][tp] * (mid - l + 1);
- add[rc][tp] += add[t][tp];
- val[rc][tp] += add[t][tp] * (r - mid);
- add[t][tp] = 0;
- }
- void update_helper(int t, int l, int r, int ql, int qr, int v, int tp) {
- if (ql <= l && r <= qr) {
- add[t][tp] += v;
- val[t][tp] += (ll)v * (r - l + 1);
- return;
- }
- if (ql > r || qr < l) return;
- pushdown(t, l, r, tp);
- int lc = t << 1, rc = t << 1 | 1, mid = (l + r) >> 1;
- update_helper(lc, l, mid, ql, qr, v, tp);
- update_helper(rc, mid + 1, r, ql, qr, v, tp);
- val[t][tp] = val[lc][tp] + val[rc][tp];
- }
- void seg_update(int l, int r, int v, int tp) {
- update_helper(1, 1, n, l, r, v, tp);
- }
- void update(int u, int v, int x, int tp) {
- while (top[u] != top[v]) {
- if (dep[top[u]] > dep[top[v]]) swap(u, v);
- seg_update(id[top[v]], id[v], x, tp);
- v = fa[top[v]];
- }
- if (dep[u] > dep[v]) swap(u, v);
- seg_update(id[u], id[v], x, tp);
- }
- ll ans0[2], ans1, cnt0[2], cnt1;
- ll query_helper(int t, int l, int r, int ql, int qr, int tp) {
- if (ql <= l && r <= qr) return val[t][tp];
- if (l > qr || r < ql) return 0;
- pushdown(t, l, r, tp);
- int lc = t << 1, rc = t << 1 | 1, mid = (l + r) >> 1;
- return query_helper(lc, l, mid, ql, qr, tp) + query_helper(rc, mid + 1, r, ql, qr, tp);
- }
- ll seg_query(int l, int r, int tp) {
- return query_helper(1, 1, n, l, r, tp);
- }
- ll query(int u, int v, int tp) {
- ll ans = 0;
- while (top[u] != top[v]) {
- if (dep[top[u]] > dep[top[v]]) swap(u, v);
- ans += seg_query(id[top[v]], id[v], tp);
- v = fa[top[v]];
- }
- if (dep[u] > dep[v]) swap(u, v);
- ans += seg_query(id[u], id[v], tp);
- return ans;
- }
- int main() {
- scanf("%d%d", &n, &m);
- for (int i = 0; i < n - 1; i++) {
- int u, v;
- scanf("%d%d", &u, &v);
- g[u].pb(v);
- g[v].pb(u);
- }
- set_parity(1, 0, 1);
- dfs1(1, 0);
- dfs2(1, 0);
- for (int i = 0; i < m; i++) {
- int op, u, x;
- scanf("%d%d", &op, &u);
- if (op == 1) {
- scanf("%d", &x);
- ans0[par[u]] += (ll)x * (dep[u] - 1);
- cnt0[par[u]] += x;
- update(1, u, x, par[u]);
- }
- else {
- ll ans;
- ans = ans0[par[u]] - 2 * query(1, u, par[u]) + 2 * query(1, 1, par[u]) + cnt0[par[u]] * (dep[u] - 1);
- printf("%lld\n", ans);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement