首页 > 代码库 > 【NOI模拟】谈笑风生(主席树)
【NOI模拟】谈笑风生(主席树)
题目描述
设 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 。
输入格式
输入的第一行含有两个正整数n和q，分别代表有根树的点数与询问的个数。
接下来 n-1 行，每行描述一条树上的边。每行含有两个整数 u 和 v ，代表在节点 u 和 v 之间有一条边。
接下来 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
题目分析
CODE:
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<algorithm>using namespace std;typedef long long ll;const int N = 300005;int n, q;#define bug(x) cout<<#x<<":"<<x<<endlinline int Re(){ int i = 0, f = 1; char ch = getchar(); for(; (ch < ‘0‘ || ch > ‘9‘) && ch != ‘-‘; ch = getchar()); if(ch == ‘-‘) f = -1, ch = getchar(); for(; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) i = (i << 3) + (i << 1) + (ch - ‘0‘); return i * f;}struct node{ int lc, rc; ll sum;}tr[N << 6];int pool, root[N], sze[N], dep[N], in[N], out[N], id;int ecnt, adj[N], go[N << 1], nxt[N << 1], maxx, pos[N];inline void Insert(const int &x, int &y, const int &l, const int &r, const int &pos, const int &v){ tr[y = ++pool] = tr[x]; tr[y].sum += v; if(l == r) return; int mid = l + r >> 1; if(pos <= mid) Insert(tr[x].lc, tr[y].lc, l, mid, pos, v); else Insert(tr[x].rc, tr[y].rc, mid + 1, r, pos, v);}inline ll query(int pos, const int &nl, const int &nr, const int &l, const int &r){ if(l <= nl && nr <= r) return tr[pos].sum; int mid = nl + nr >> 1; ll ret = 0; if(l <= mid) ret += query(tr[pos].lc, nl, mid, l, r); if(r > mid ) ret += query(tr[pos].rc, mid + 1, nr, l, r); return ret;}inline void addEdge(const int &u, const int &v){ nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v; nxt[++ecnt] = adj[v], adj[v] = ecnt, go[ecnt] = u;}inline void dfs(const int &u, const int &f){ dep[u] = dep[f] + 1; maxx = max(maxx, dep[u]); sze[u] = 1; in[u] = ++id; pos[id] = u; int v; for(int e = adj[u]; e; e = nxt[e]){ if((v = go[e]) == f) continue; dfs(v, u); sze[u] += sze[v]; } out[u] = id;}inline void tree_init(){ for(int i = 1; i <= n; i++){ Insert(root[i - 1], root[i], 0, maxx, dep[pos[i]], sze[pos[i]] - 1); }}int main(){ freopen("h.in", "r", stdin); n = Re(), q = Re(); for(int i = 1; i < n; i++){ int u = Re(), v = Re(); addEdge(u, v); } maxx = -1; dep[0] = -1; dfs(1, 0); tree_init();// for(int i = 1; i <= n; i++) bug(i),bug(dep[pos[i]]); for(int i = 1; i <= q; i++){ int p = Re(); int k = Re(); ll ans = 0; ans += (ll)(sze[p] - 1) * (ll)min(dep[p], k); // bug(ans); ans += query(root[out[p]], 0, maxx, min(dep[p] + 1, maxx), min(dep[p] + k, maxx)); // bug(ans); bug(query(root[out[p]], 1, maxx, min(dep[p] + 1, maxx), min(dep[p] + k, maxx))); ans -= query(root[in[p] - 1], 0, maxx, min(dep[p] + 1, maxx), min(dep[p] + k, maxx)); cout<<ans<<endl; } return 0;}
【NOI模拟】谈笑风生(主席树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。