#include <algorithm> #include <cstdio> #include <iostream> #include <vector> using namespace std;
const int SIZE = 1e5 + 10; struct EDGE { int v, nxt; } edge[SIZE << 1]; int head[SIZE], cnt; void add_edge(int u, int v) { edge[++cnt].v = v; edge[cnt].nxt = head[u]; head[u] = cnt; } struct Query { int p, u, id, op; Query(int p = 0, int u = 0, int id = 0, int op = 0) : p(p), u(u), id(id), op(op) {} bool operator<(const Query& b) const { return p < b.p; } }; namespace HLD { int siz[SIZE], deep[SIZE], fa[SIZE], hson[SIZE]; int top[SIZE], dfn[SIZE], rnk[SIZE], tot; void dfs1(int u, int dep) { siz[u] = 1; deep[u] = dep; for(int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].v; if(deep[v]) continue; dfs1(v, dep + 1); fa[v] = u; siz[u] += siz[v]; if(siz[v] > siz[hson[u]]) hson[u] = v; } } void dfs2(int u, int t) { top[u] = t; dfn[u] = ++tot; rnk[tot] = u; if(hson[u]) dfs2(hson[u], t); for(int i = head[u]; i; i = edge[i].nxt) if(edge[i].v != fa[u] && edge[i].v != hson[u]) dfs2(edge[i].v, edge[i].v); } int LCA(int a, int b) { while(top[a] != top[b]) { if(deep[top[a]] < deep[top[b]]) swap(a, b); a = fa[top[a]]; } return deep[a] < deep[b] ? a : b; } void prework() { dfs1(1, 1); dfs2(1, 1); } } using namespace HLD; namespace HJT { struct Laffey { int ls, rs; int cnt; #define ls(i) (tree[i].ls) #define rs(i) (tree[i].rs) } tree[SIZE << 5]; int root[SIZE], postot; void add(int nl, int nr, int s, int last, int& i, int k) { i = ++postot; tree[i] = tree[last]; tree[i].cnt += k; if(nl == nr) return; int mid = (nl + nr) >> 1; if(s <= mid) add(nl, mid, s, ls(last), ls(i), k); else add(mid + 1, nr, s, rs(last), rs(i), k); } int query(int nl, int nr, int l, int r, int p, int q) { if(nl >= l && nr <= r) return tree[q].cnt - tree[p].cnt; int mid = (nl + nr) >> 1; int sum = 0; if(mid >= l) sum += query(nl, mid, l, r, ls(p), ls(q)); if(mid + 1 <= r) sum += query(mid + 1, nr, l, r, rs(p), rs(q)); return sum; } #undef ls #undef rs } using namespace HJT; namespace SegmentTree { struct Laffey { #define ls(i) (i << 1) #define rs(i) (i << 1 | 1) int l, r; int sum, add; Laffey(int l = 0, int r = 0, int sum = 0, int add = 0) : l(l), r(r), sum(sum), add(add) {} int len() { return r - l + 1; } } tree[SIZE << 2]; void push_up(int i) { tree[i].sum = tree[ls(i)].sum + tree[rs(i)].sum; } void update(int i, int k) { tree[i].sum += tree[i].len() * k; tree[i].add += k; } void push_down(int i) { if(!tree[i].add) return; update(ls(i), tree[i].add); update(rs(i), tree[i].add); tree[i].add = 0; } void build(int l, int r, int i) { tree[i].l = l, tree[i].r = r; if(l == r) return; int mid = (l + r) >> 1; build(l, mid, ls(i)); build(mid + 1, r, rs(i)); } void add(int l, int r, int i, int k) { if(tree[i].l >= l && tree[i].r <= r) { update(i, k); return; } push_down(i); if(tree[ls(i)].r >= l) add(l, r, ls(i), k); if(tree[rs(i)].l <= r) add(l, r, rs(i), k); push_up(i); } int query(int l, int r, int i) { if(tree[i].l >= l && tree[i].r <= r) return tree[i].sum; push_down(i); int sum = 0; if(tree[ls(i)].r >= l) sum += query(l, r, ls(i)); if(tree[rs(i)].l <= r) sum += query(l, r, rs(i)); return sum; } #undef ls #undef rs } using namespace SegmentTree; int f[20][SIZE], pre[SIZE]; int ans[SIZE]; vector<Query> q; int main() { int n, m; cin >> n >> m; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; add_edge(u, v); add_edge(v, u); } HLD::prework(); SegmentTree::build(1, n, 1); for(int i = 1; i <= n; i++) f[0][i] = fa[i], pre[i] = pre[i - 1] + deep[i]; for(int i = 1; i <= 19; i++) for(int j = 1; j <= n; j++) f[i][j] = f[i - 1][f[i - 1][j]]; for(int i = 1; i <= n; i++) HJT::add(1, n, rnk[i], root[i - 1], root[i], 1); for(int i = 1; i <= m; i++) { int l, r; cin >> l >> r; int L = 1, R = n; int goal = r - l + 1; while(R - L > 0) { int mid = (L + R) >> 1; if(goal <= HJT::query(1, n, l, r, root[0], root[mid]) * 2) R = mid; else L = mid + 1; } int u = rnk[R]; for(int j = 19; j >= 0; j--) if(f[j][u] && query(1, n, l, r, root[dfn[f[j][u]] - 1], root[dfn[f[j][u]] + siz[f[j][u]] - 1]) * 2 < goal) u = f[j][u]; if(HJT::query(1, n, l, r, root[dfn[u] - 1], root[dfn[u] + siz[u] - 1]) * 2 <= goal) u = fa[u]; ans[i] = pre[r] - pre[l - 1] + (r - l + 1) * deep[u]; q.emplace_back(l - 1, u, i, 2), q.emplace_back(r, u, i, -2); } sort(q.begin(), q.end()); int now = 0; for(auto v : q) { while(now < v.p) { now++; int u = now; while(u) { SegmentTree::add(dfn[top[u]], dfn[u], 1, 1); u = fa[top[u]]; } } int u = v.u; while(u) { ans[v.id] += v.op * SegmentTree::query(dfn[top[u]], dfn[u], 1); u = fa[top[u]]; } } for(int i = 1; i <= m; i++) cout << ans[i] << endl; return 0; }
|