Today Menu asked a question on slack:
Consider a tree where every single node has an associated range. For all nodes u, output the number of nodes v such that the intersection of ranges on all nodes on the path from u to v is non-empty. Any ideas?
I thought about it for a long time and only came up with an $O(n\log^2)$ algorithm:
First, only consider paths that pass through the root.
- dfs from the root to get the range of each node.
- For each node $u$, calculate the number of intersecting paths with it.
- However, this might result in duplicates. For example, the path u->root->u is equivalent to u->root, and gets counted twice.
So for each node, calculate two values:
a. The number of intersecting paths from node u to all nodes in the tree.
b. The number of paths from node u to nodes within its subtree.
Let f(u, rt) represent the number of paths from u to nodes in the subtree rooted at rt, the number of paths starting from u and passing through root is f(u, root) – f(u, root.child). - The calculation of the number of intersecting intervals can be implemented through preprocessing, sorting, and then binary search. Suppose we want to query $(ql, qr)$ in an array $[(l_i, r_i)]$. Put all $l_i$ in an array $lt$, and all $r_i$ in another array $rt$, and then sort them. Each time query, binary search on both arrays to find the count of $l_i > qr$ and $r_i < ql$, and subtract these from the total.
- Then centroid decomposition
Similar to tree divide and conquer, but the tree might be very unbalanced. Recursively process each subtree, but before doing so, find the centroid to reconstruct the subtree with the centroid as its root. According to the master theorem, the complexity is $O(n\log^2)$
// compile: make data
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
std::ifstream terminal("/dev/tty");
#define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore();
#else
#define debug(x...)
#define Debug(x...)
#define PP
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x),__VA_ARGS__})
#define cmax(x,...) x=max({(x),__VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define int long long
#define uint unsigned long long
#define MAXN 200010
struct Tree {
int n;
vector<vector<int>> e;
struct node {
vector<node*> ch;
node *parent = nullptr;
int size, depth, height, val, dfn;
node *heavy = nullptr, *top = nullptr;
int wl, wr;
int l, r;
};
vector<node> vertex;
vector<int> removed;
node *root;
Tree(int V) {
n = V;
e.resize(n);
vertex.resize(n);
removed.resize(n);
}
void add_edge(int u, int v) {
e[u].push_back(v), e[v].push_back(u);
}
int ind(node *x) {return x - &vertex[0]; }
void setroot(int rt = 0) {
if (root != &vertex[rt]) build(rt);
root = &vertex[rt];
}
void build(int rt = 0) {
function<void(int, int, int, int)> dfs = [&](int u, int pre, int curl, int curr) {
node *x = &vertex[u];
x->size = 1;
x->depth = !~pre ? 0 : vertex[pre].depth + 1;
x->height = 1;
x->ch.clear();
if (~curl && ~curr && (curl <= x->wr || curr >= x->wl)) x->l = max(x->wl, curl), x->r = min(x->wr, curr);
if ((!~curl && !~curr) || x->l > x->r) x->l = x->r = -1;
for (int v: e[u]) {
if (v == pre || removed[v]) continue;
node *y = &vertex[v];
x->ch.push_back(y);
y->parent = x;
dfs(v, u, x->l, x->r);
x->size += y->size;
if (!x->heavy || y->size > x->heavy->size) x->heavy = y;
cmax(x->height, y->height + 1);
}
};
dfs(rt, -1, -INF, INF);
}
int centroid(int r = -1) {
if (~r) build(r);
else r = ind(root);
int N = vertex[r].size;
if (N <= 2) return r;
for (node *x = &vertex[r]; x; ) {
int maxsz = -INF;
node *maxnode = nullptr;
for (auto y: x->ch) if (y->size > maxsz) maxsz = y->size, maxnode = y;
if (maxsz <= N / 2) return ind(x);
x = maxnode;
}
return r;
}
void centroid_decomp(auto solve) {
auto getvs = [&](int u) -> vector<int> {
vector<int> vs;
queue<int> q; q.push(u);
while (!q.empty()) {
int x = q.front(); q.pop();
vs.push_back(x);
for (auto y: vertex[x].ch) q.push(ind(y));
}
return vs;
};
function<void(node*)> dfs = [&](node *x) -> void {
int c = centroid(ind(x));
if(c != ind(x)) build(c);
vector<vector<int>> vs;
for (auto y: vertex[c].ch) vs.push_back(getvs(ind(y)));
solve(c, vs);
removed[c] = 1, vertex[c].ch.clear();
for (auto v: e[c]) if (!removed[v]) dfs(&vertex[v]);
};
dfs(root);
}
void graphviz_dump(int plus = 0, string filename = "graph.dot") {
string vlabel = "", elabel = "";
elabel = " color=\"red\"";
set<int> vset; set<pair<int, int>> eset;
rep(i, 0, n) if (vertex[i].heavy) vset.insert(ind(vertex[i].heavy)), eset.insert({i, ind(vertex[i].heavy)});
FILE *f = fopen(filename.c_str(), "w");
fprintf(f, "digraph Tree {\n");
rep(i, 0, n) {
node *x = &vertex[i];
fprintf(f, " %lld[label=\"%lld", i, i+plus);
vector<string> desired = {
"l=" + to_string(x->l),
"r=" + to_string(x->r),
};
for (auto s: desired) fprintf(f, " | %s", s.c_str());
fprintf(f, "\" shape=\"record\"%s];\n", vset.count(i) ? vlabel.c_str() : "");
}
rep(i, 0, n) {
node *x = &vertex[i];
for (auto y: x->ch) {
fprintf(f, " %ld -> %ld[arrowhead=\"none\"%s];\n", x - &vertex[0], y - &vertex[0], eset.count({i, ind(y)}) ? elabel.c_str() : "");
}
}
fprintf(f, "}\n");
fclose(f);
}
};
int count_pairs(vector<int> <, vector<int> &rt, pair<int, int> q) {
auto bslt = [&](int x) {
int l = 0, r = sz(rt)-1, ans = -1;
while (l <= r) {
int mid = l + (r-l) / 2;
if (rt[mid] >= x) r = mid - 1;
else ans = mid, l = mid + 1;
}
return ans;
};
auto bsgt = [&](int x) {
int l = 0, r = sz(lt)-1, ans = -1;
while (l <= r) {
int mid = l + (r-l) / 2;
if (lt[mid] <= x) l = mid + 1;
else ans = mid, r = mid - 1;
}
return ans;
};
int l = bsgt(q.second); l = ~l ? sz(lt)-l : 0;
int r = bslt(q.first); r = ~r ? r+1 : 0;
return sz(lt) - l - r;
}
bool intersect(pair<int, int> a, pair<int, int> b) {
return (a.first > b.second || a.second < b.first) ? 0 : 1;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n; cin >> n;
Tree t(n);
rep(i, 0, n) cin >> t.vertex[i].wl >> t.vertex[i].wr;
rep(i, 0, n-1) {
int u, v; cin >> u >> v;
t.add_edge(u, v);
}
t.setroot(0);
vector<int> ans(n, 0);
auto solve = [&](int root, vector<vector<int>> &subtrees) -> void {
vector<int> glt, grt;
glt.push_back(t.vertex[root].l), grt.push_back(t.vertex[root].r);
ans[root] += 1;
for (auto &v: subtrees) for (auto &u: v) if (~t.vertex[u].l && ~t.vertex[u].r) {
glt.push_back(t.vertex[u].l), grt.push_back(t.vertex[u].r);
ans[root] += intersect({t.vertex[u].l, t.vertex[u].r}, {t.vertex[root].l, t.vertex[root].r});
}
sort(glt.begin(), glt.end()); sort(grt.begin(), grt.end());
for (auto &v: subtrees) {
vector<int> slt, srt;
for (auto &u: v) if (~t.vertex[u].l && ~t.vertex[u].r) slt.push_back(t.vertex[u].l), srt.push_back(t.vertex[u].r);
sort(slt.begin(), slt.end()); sort(srt.begin(), srt.end());
for (auto &u: v) {
pair<int, int> q = {t.vertex[u].l, t.vertex[u].r};
ans[u] += count_pairs(glt, grt, q) - count_pairs(slt, srt, q);
}
}
};
t.centroid_decomp(solve);
for (auto i: ans) cout << i << endl;
return 0;
}