1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
| // __________________
// | ________________ |
// || ____ ||
// || /\ | ||
// || /__\ | ||
// || / \ |____ ||
// ||________________||
// |__________________|
// \###################\
// \###################\
// \ ____ \
// \_______\___\_______\
// An AC a day keeps the doctor away.
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma loop_opt(on)
#include <bits/extc++.h>
#ifdef local
#define debug(x) (cerr<<#x<<" = "<<(x)<<'\n')
#else
#define debug(x) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define pb emplace_back
#define ff first
#define ss second
#define mid (l+(r-l>>1))
#define mem(v,x) memset(v,x,sizeof v)
#define int ll
using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
constexpr ld PI = acos(-1), eps = 1e-9;
constexpr ll N = 100025, INF = 1e18, MOD = 20191126, K = 20, inf = 1e9;
constexpr ll modpow(ll e,ll p,ll m=MOD) {ll r=1; for(;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r;}
constexpr inline ll cdiv(ll x, ll m) { return (x+m-1)/m; } // ceiling divide, x/m for flooring divide
template <typename T> void M(T &x, ll m=MOD){x%=m; if(x<0) x+=m;}
struct Edge {
ll v,w; // v=a^b
} E[N];
int vis[N],sz[N],mxs[N],cpa[N],cdep[N];
ll dis[K][N];
vector<int> g[N],tmp;
void dfs(int u) {
vis[u] = true, mxs[u] = 0, sz[u] = 1;
tmp.pb(u);
for(int id:g[u]) {
int v = E[id].v^u;
if(!vis[v]) dfs(v), mxs[u] = max(mxs[u], sz[v]), sz[u] += sz[v];
}
}
void get_dis(int u,int d) { // get distance to centroid whose depth is d
vis[u] = true;
for(int id:g[u]) {
int v = E[id].v^u;
if(!vis[v]) dis[d][v] = dis[d][u]+E[id].w, get_dis(v,d);
}
}
void deco(int u,int dep=1,int pa=0) { // centroid decomposition
tmp.clear();
dfs(u);
int c = u, S = tmp.size();
for(int i:tmp) {
if(max(S-sz[i],mxs[i]) < max(S-sz[c], mxs[c])) c = i;
vis[i] = 0;
}
dis[dep][c] = 0;
get_dis(c,dep);
for(int i:tmp) vis[i] = 0;
vis[c] = true;
cpa[c] = pa;
cdep[c] = dep;
for(int id:g[c]) {
int v = E[id].v^c;
if(!vis[v]) deco(v,dep+1,c);
}
}
ll ans[N],re[N],cnt[N];
void update(int p) {
for(int x = p, d = cdep[p]; x; x = cpa[x], --d) {
ans[x] += dis[d][p];
re[x] += dis[d-1][p];
++cnt[x];
}
}
ll query(int p) {
ll res = 0, now = 0;
for(int x = p, d = cdep[p]; x; x = cpa[x], --d) {
res += (ans[x] - re[x]) + (cnt[x] - now) * dis[d][p];
now = cnt[x];
}
return res;
}
bitset<N> color;
signed main() {
int n,q;
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
for(int i = 0,a,b,w; i < n-1; i++) {
cin >> a >> b >> w, a++, b++;
E[i] = {a^b,w};
g[a].pb(i), g[b].pb(i);
}
deco(1);
//for(int i = 1; i <= n; i++) cout << cpa[i] << " \n"[i==n];
//for(int i = 1; i <= n; i++) cout << cdep[i] << " \n"[i==n];
//for(int i = 1; i <= n; i++) cout << dis[1][i] << " \n"[i==n];
while(q--) {
int t,v;
cin >> t >> v, v++;
if(t == 2) cout << query(v) << '\n';
else if(t == 1 && !color[v]) color[v] = true, update(v);
//for(int i = 1; i <= n; i++) cout<<ans[i]<<" \n"[i==n];
}
}
|
