library
This documentation is automatically generated by online-judge-tools/verification-helper
Contour Sum Query
(Graph/contour.hpp)
- View this file on GitHub
- Last update: 2024-01-14 02:07:43+09:00
- Include:
#include "Graph/contour.hpp"
Depends on
Verified with
Code
#pragma once
#include "Graph/centroid.hpp"
#include "Graph/hld.hpp"
struct ContourQuery {
using P = pair<int, int>;
using T = pair<int, P>;
ContourQuery(int _n = 0)
: n(_n), m(_n), cd(_n), hld(_n), tree(_n * 3), depth(_n * 3),
base(_n * 3), parent(_n * 3, -1), buf(_n * 3), width(_n * 3, 1),
seg(_n * 3) {}
void add_edge(int u, int v) {
cd.add_edge(u, v);
hld.add_edge(u, v);
}
vector<int> run() {
hld.run();
root = rec(0);
depth[0] = 0;
dfs(0, -1);
rep(v, 0, m) if (v != root) { seg[v] = width[v]; }
return seg;
}
vector<P> point(int v) {
vector<P> ret;
int cur = v;
while (cur != root) {
int D =
depth[v] + depth[base[cur]] - 2 * depth[hld.lca(v, base[cur])];
ret.push_back({cur, D});
cur = parent[cur];
}
return ret;
}
vector<T> range(int v, int L, int R) {
vector<T> ret;
if (L <= 0 and 0 < R)
ret.push_back({v, {0, 1}});
int cur = parent[v], pre = v;
while (pre != root) {
int bro = -1;
for (auto &to : tree[cur])
if (to != parent[cur] and to != pre) {
bro = to;
break;
}
if (bro != -1) {
int D = depth[v] + depth[base[bro]] -
2 * depth[hld.lca(v, base[bro])];
ret.push_back(
{bro,
{clamp(L - D, 0, seg[bro]), clamp(R - D, 0, seg[bro])}});
}
pre = cur;
cur = parent[cur];
}
return ret;
}
private:
int n, m, root;
CentroidDecomposition cd;
HLD hld;
vector<vector<int>> tree;
vector<int> depth, base, parent, buf, width, seg;
int rec(int rt) {
int cen = cd.find(rt);
buf[cen] = 1;
queue<P> que;
auto cmp = [&](int u, int v) { return buf[u] > buf[v]; };
priority_queue<int, vector<int>, decltype(cmp)> pq{cmp};
pq.push(cen);
depth[cen] = 0;
base[cen] = cen;
for (auto &to : cd.g[cen])
if (!cd.used[to]) {
int v = rec(to);
que.push({to, cen});
depth[to] = 1;
while (!que.empty()) {
auto [cur, par] = que.front();
que.pop();
width[v] = depth[cur] + 1;
for (auto &nxt : cd.g[cur])
if (nxt != par and !cd.used[nxt]) {
depth[nxt] = depth[cur] + 1;
que.push({nxt, cur});
}
}
pq.push(v);
base[v] = cen;
}
cd.used[cen] = 0;
if (pq.size() > 1) {
for (;;) {
int v1 = pq.top();
pq.pop();
int v2 = pq.top();
pq.pop();
int extra = m++;
tree[extra].push_back(v1);
tree[extra].push_back(v2);
tree[v1].push_back(extra);
tree[v2].push_back(extra);
buf[extra] = buf[v1] + buf[v2];
parent[v1] = parent[v2] = extra;
if (pq.empty()) {
return extra;
}
pq.push(extra);
base[extra] = cen;
width[extra] = max(width[v1], width[v2]);
}
} else {
int extra = m++;
tree[extra].push_back(cen);
tree[cen].push_back(extra);
buf[extra] = 1;
parent[cen] = extra;
return extra;
}
}
void dfs(int v, int p) {
for (auto &to : cd.g[v])
if (to != p) {
depth[to] = depth[v] + 1;
dfs(to, v);
}
}
};
/**
* @brief Contour Sum Query
*/#line 2 "Graph/centroid.hpp"
class CentroidDecomposition{
void get(int v,int p){
sz[v]=1;
for(auto& to:g[v])if(to!=p and !used[to]){
get(to,v);
sz[v]+=sz[to];
}
}
int dfs(int v,int p,int rt){
for(auto& to:g[v])if(to!=p and !used[to]){
if(sz[to]>(sz[rt]>>1))return dfs(to,v,rt);
}
return v;
}
public:
int n;
vector<vector<int>> g;
vector<int> sz,used;
CentroidDecomposition(int n_):n(n_),g(n),sz(n),used(n){}
void add_edge(int u,int v){
g[u].push_back(v);
g[v].push_back(u);
}
int find(int rt){
get(rt,-1);
int res=dfs(rt,-1,rt);
used[res]=1;
return res;
}
};
/**
* @brief Centroid Decomposition
*/
#line 2 "Graph/hld.hpp"
struct HLD{
using P=pair<int,int>;
vector<vector<int>> g; vector<int> sz,in,out,rev,hs,par,dist;
void dfs(int v,int p){
par[v]=p; sz[v]=1;
if(p!=-1)dist[v]=dist[p]+1;
if(!g[v].empty() and g[v][0]==p)swap(g[v][0],g[v].back());
for(auto& to:g[v])if(to!=p){
dfs(to,v); sz[v]+=sz[to];
if(sz[g[v][0]]<sz[to])swap(g[v][0],to);
}
}
void dfs2(int v,int p,int& k){
in[v]=k++; rev[in[v]]=v;
for(auto& to:g[v])if(to!=p){
hs[to]=(g[v][0]==to?hs[v]:to);
dfs2(to,v,k);
}
out[v]=k;
}
HLD(int _n):g(_n),sz(_n),in(_n),out(_n),rev(_n),hs(_n),par(_n),dist(_n){}
void add_edge(int u,int v){
g[u].emplace_back(v); g[v].emplace_back(u);
}
void run(int rt=0){dfs(rt,-1); hs[rt]=rt; int k=0; dfs2(rt,-1,k);}
int lca(int u,int v){
for(;;v=par[hs[v]]){
if(in[u]>in[v])swap(u,v);
if(hs[u]==hs[v])return u;
}
}
vector<P> get(int u,int p,bool es=0){
assert(in[p]<=in[u] and out[u]<=out[p]);
vector<P> res;
while(hs[u]!=hs[p]){
res.push_back({in[hs[u]],in[u]+1});
u=par[hs[u]];
}
res.push_back({in[p]+es,in[u]+1});
return res;
}
int jump(int u,int v,int k){
if(k<0)return -1;
int g=lca(u,v);
int d0=dist[u]+dist[v]-dist[g]*2;
if(d0<k)return -1;
int st=u;
if(dist[u]-dist[g]<k)st=v,k=d0-k;
for(;;){
int to=hs[st];
if(in[st]-k>=in[to])return rev[in[st]-k];
k-=in[st]-in[to]+1; st=par[to];
}
}
};
/**
* @brief Heavy Light Decomposition
*/
#line 4 "Graph/contour.hpp"
struct ContourQuery {
using P = pair<int, int>;
using T = pair<int, P>;
ContourQuery(int _n = 0)
: n(_n), m(_n), cd(_n), hld(_n), tree(_n * 3), depth(_n * 3),
base(_n * 3), parent(_n * 3, -1), buf(_n * 3), width(_n * 3, 1),
seg(_n * 3) {}
void add_edge(int u, int v) {
cd.add_edge(u, v);
hld.add_edge(u, v);
}
vector<int> run() {
hld.run();
root = rec(0);
depth[0] = 0;
dfs(0, -1);
rep(v, 0, m) if (v != root) { seg[v] = width[v]; }
return seg;
}
vector<P> point(int v) {
vector<P> ret;
int cur = v;
while (cur != root) {
int D =
depth[v] + depth[base[cur]] - 2 * depth[hld.lca(v, base[cur])];
ret.push_back({cur, D});
cur = parent[cur];
}
return ret;
}
vector<T> range(int v, int L, int R) {
vector<T> ret;
if (L <= 0 and 0 < R)
ret.push_back({v, {0, 1}});
int cur = parent[v], pre = v;
while (pre != root) {
int bro = -1;
for (auto &to : tree[cur])
if (to != parent[cur] and to != pre) {
bro = to;
break;
}
if (bro != -1) {
int D = depth[v] + depth[base[bro]] -
2 * depth[hld.lca(v, base[bro])];
ret.push_back(
{bro,
{clamp(L - D, 0, seg[bro]), clamp(R - D, 0, seg[bro])}});
}
pre = cur;
cur = parent[cur];
}
return ret;
}
private:
int n, m, root;
CentroidDecomposition cd;
HLD hld;
vector<vector<int>> tree;
vector<int> depth, base, parent, buf, width, seg;
int rec(int rt) {
int cen = cd.find(rt);
buf[cen] = 1;
queue<P> que;
auto cmp = [&](int u, int v) { return buf[u] > buf[v]; };
priority_queue<int, vector<int>, decltype(cmp)> pq{cmp};
pq.push(cen);
depth[cen] = 0;
base[cen] = cen;
for (auto &to : cd.g[cen])
if (!cd.used[to]) {
int v = rec(to);
que.push({to, cen});
depth[to] = 1;
while (!que.empty()) {
auto [cur, par] = que.front();
que.pop();
width[v] = depth[cur] + 1;
for (auto &nxt : cd.g[cur])
if (nxt != par and !cd.used[nxt]) {
depth[nxt] = depth[cur] + 1;
que.push({nxt, cur});
}
}
pq.push(v);
base[v] = cen;
}
cd.used[cen] = 0;
if (pq.size() > 1) {
for (;;) {
int v1 = pq.top();
pq.pop();
int v2 = pq.top();
pq.pop();
int extra = m++;
tree[extra].push_back(v1);
tree[extra].push_back(v2);
tree[v1].push_back(extra);
tree[v2].push_back(extra);
buf[extra] = buf[v1] + buf[v2];
parent[v1] = parent[v2] = extra;
if (pq.empty()) {
return extra;
}
pq.push(extra);
base[extra] = cen;
width[extra] = max(width[v1], width[v2]);
}
} else {
int extra = m++;
tree[extra].push_back(cen);
tree[cen].push_back(extra);
buf[extra] = 1;
parent[cen] = extra;
return extra;
}
}
void dfs(int v, int p) {
for (auto &to : cd.g[v])
if (to != p) {
depth[to] = depth[v] + 1;
dfs(to, v);
}
}
};
/**
* @brief Contour Sum Query
*/