首页 > 代码库 > [BZOJ3653]谈笑风生
[BZOJ3653]谈笑风生
[BZOJ3653]谈笑风生
试题描述
设T 为一棵有根树,我们做如下的定义:
? 设a和b为T 中的两个不同节点。如果a是b的祖先,那么称“a比b不知道
高明到哪里去了”。
? 设a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定
常数x,那么称“a 与b 谈笑风生”。
给定一棵n个节点的有根树T,节点的编号为1 到 n,根节点为1号节点。你需
要回答q 个询问,询问给定两个整数p和k,问有多少个有序三元组(a;b;c)满足:
1. a、b和 c为 T 中三个不同的点,且 a为p 号节点;
2. a和b 都比 c不知道高明到哪里去了;
3. a和b 谈笑风生。这里谈笑风生中的常数为给定的 k。
? 设a和b为T 中的两个不同节点。如果a是b的祖先,那么称“a比b不知道
高明到哪里去了”。
? 设a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定
常数x,那么称“a 与b 谈笑风生”。
给定一棵n个节点的有根树T,节点的编号为1 到 n,根节点为1号节点。你需
要回答q 个询问,询问给定两个整数p和k,问有多少个有序三元组(a;b;c)满足:
1. a、b和 c为 T 中三个不同的点,且 a为p 号节点;
2. a和b 都比 c不知道高明到哪里去了;
3. a和b 谈笑风生。这里谈笑风生中的常数为给定的 k。
输入
输入文件的第一行含有两个正整数n和q,分别代表有根树的点数与询问的个数。接下来n - 1行,每行描述一条树上的边。每行含有两个整数u和v,代表在节点u和v之间有一条边。
接下来q行,每行描述一个操作。第i行含有两个整数,分别表示第i个询问的p和k。
接下来q行,每行描述一个操作。第i行含有两个整数,分别表示第i个询问的p和k。
输出
输出 q 行,每行对应一个询问,代表询问的答案。
输入示例
5 3 1 2 1 3 2 4 4 5 2 2 4 1 2 3
输出示例
3 1 3
数据规模及约定
1<=P<=N
1<=K<=N
N<=300000
Q<=300000
题解
我们发现询问的答案分为两部分:b 是 a 的祖先;a 是 b 的祖先。
对于 b 是 a 的祖先的情况,这一部分的答案直接就是 min{ (dep[b] - 1), k } * (siz[a] - 1),就是先确定 b 在哪(可以在 a 到根节点的路径上,但要保证 a 与 b 距离不超过 k),再确定 c 在哪(可以发现 a 子树中除 a 外的所有节点都可以取到)。
对于 a 是 b 的祖先的情况,我们发现 b 的深度范围在区间 ( dep[a], dep[a] + k ] 内,每个 b 所对应的 c 都可以是 b 的子树除 b 外的所有节点;于是我们可以使用 dfs 序 + 主席树维护这个东西。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> using namespace std; const int BufferSize = 1 << 16; char buffer[BufferSize], *Head, *Tail; inline char Getchar() { if(Head == Tail) { int l = fread(buffer, 1, BufferSize, stdin); Tail = (Head = buffer) + l; } return *Head++; } int read() { int x = 0, f = 1; char c = Getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); } return x * f; } #define maxn 300010 #define maxm 600010 #define maxnode 6000010 #define LL long long int n, m, head[maxn], nxt[maxm], to[maxm]; void AddEdge(int a, int b) { to[++m] = b; nxt[m] = head[a]; head[a] = m; swap(a, b); to[++m] = b; nxt[m] = head[a]; head[a] = m; return ; } int siz[maxn], dep[maxn], dl[maxn], dr[maxn], uid[maxn], clo; void build(int u, int fa) { dl[u] = ++clo; uid[clo] = u; siz[u] = 1; for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa) { dep[to[e]] = dep[u] + 1; build(to[e], u); siz[u] += siz[to[e]]; } dr[u] = clo; return ; } int rt[maxn], ToT, lc[maxnode], rc[maxnode]; LL sumv[maxnode]; void update(int& y, int x, int l, int r, int p, int v) { sumv[y = ++ToT] = sumv[x] + v; if(l == r) return ; int mid = l + r >> 1; lc[y] = lc[x]; rc[y] = rc[x]; if(p <= mid) update(lc[y], lc[x], l, mid, p, v); else update(rc[y], rc[x], mid + 1, r, p, v); return ; } LL query(int o, int l, int r, int ql, int qr) { if(!o) return 0; if(ql <= l && r <= qr) return sumv[o]; int mid = l + r >> 1; LL ans = 0; if(ql <= mid) ans += query(lc[o], l, mid, ql, qr); if(qr > mid) ans += query(rc[o], mid + 1, r, ql, qr); return ans; } int main() { n = read(); int q = read(); for(int i = 1; i < n; i++) { int a = read(), b = read(); AddEdge(a, b); } dep[1] = 1; build(1, 0); for(int i = 1; i <= clo; i++) update(rt[i], rt[i-1], 1, n, dep[uid[i]], siz[uid[i]] - 1); while(q--) { int u = read(), k = read(); LL ans = (LL)(siz[u] - 1) * min(k, dep[u] - 1); ans += query(rt[dr[u]], 1, n, dep[u] + 1, dep[u] + k) - query(rt[dl[u]-1], 1, n, dep[u] + 1, dep[u] + k); printf("%lld\n", ans); } return 0; }
[BZOJ3653]谈笑风生
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。