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
| namespace Heavy_Light_Decomp{
inline int dfs(int u, int fa,int depth=1){
pa[u] = fa;
dep[u] = depth;
sz[u] = 1;
for(int i=head[u];i;i=edge[i].nxt){
int v = edge[i].v;
if (v==fa) continue;
sz[u]+=dfs(v,u,depth+1);
if (sz[v]>sz[son[u]]) son[u] = v;
}
return sz[u];
}
inline void HLD(int u, int tp){
id[u] = ++cnt;
val[cnt] = pos[u];
top[u] = tp;
if (!son[u]) return;
HLD(son[u],tp);
for (int i=head[u];i;i=edge[i].nxt){
int v = edge[i].v;
if (v==pa[u] || v==son[u]) continue;
HLD(v,v);
}
}
inline bool qPath(int u, int v, int val){
int ans = 0;
while(top[u]!=top[v]){
if (dep[top[u]]<dep[top[v]]) swap(u,v);
ans +=query(1,1,n,id[top[u]],id[u],val);
u = pa[top[u]];
}
if (dep[u]>dep[v]) swap(u,v);
ans+=query(1,1,n,id[u],id[v],val);
return ans;
}
}
|
