牛客NOIP提高组R1 C保护(主席树)
2018-09-18 06:24:26来源:博客园 阅读 ()
题意
题目链接
Sol
Orz lyq
我们可以把一支军队(u, v)拆分为两个(u, lca)和(v, lca)
考虑一个点x,什么时候军队对它有贡献,肯定是u或v在他的子树内,且lca在他的子树外
因为需要让至少k个军队能够完全覆盖,所以肯定是选深度第k小的
这个过程可以用dfs序+主席树来实现
拿(u, lca)来说,在dfn[u]对应的线段树中,dep[lca]处+1即可。
然后查第k大即可
/**/ #include<cstdio> #include<vector> using namespace std; const int MAXN = 2 * 1e5 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; struct Node { int siz; }T[MAXN * 70]; int root[MAXN * 70], ls[MAXN * 70], rs[MAXN * 70]; int dep[MAXN], fa[MAXN], top[MAXN], siz[MAXN], son[MAXN], deep[MAXN], dfn[MAXN], cnt, tot, num, ID[MAXN]; vector<int> v[MAXN], Q[MAXN];//Q[i] dfs搴忎负i鐨勯渶瑕佸姞鍏ョ殑鍏冪礌 void dfs1(int x, int _fa) { dfn[x] = ++cnt; fa[x] = _fa; siz[x]= 1; deep[x] = deep[_fa] + 1; for(int i = 0; i < (int)v[x].size(); i++) { int to = v[x][i]; if(to == _fa) continue; dfs1(to, x); siz[x] += siz[to]; if(siz[to] > siz[son[x]]) son[x] = to; } } void dfs2(int x, int topf) { top[x] = topf; if(!son[x]) return ; dfs2(son[x], topf); for(int i = 0; i < (int)v[x].size(); i++) { int to = v[x][i]; if(top[to]) continue; dfs2(to, to); } } int LCA(int x, int y) { while(top[x] != top[y]) { if(deep[top[x]] < deep[top[y]]) swap(x, y); x = fa[top[x]]; } if(deep[x] > deep[y]) swap(x, y); return x; } void Insert(int &k, int p, int l, int r, int pos) { if(l > r) return ; if(!k) k = ++tot, T[k].siz = T[p].siz + 1; if(l == r) return ; int mid = (l + r) >> 1; if(pos <= mid) rs[k] = rs[p], Insert(ls[k], ls[p], l, mid, pos); else ls[k] = ls[p], Insert(rs[k], rs[p], mid + 1, r, pos); } int Query(int rl, int rr, int k, int l, int r) { if(T[rr].siz - T[rl].siz < k) return 0; if(l == r) return k > (T[rr].siz - T[rl].siz) ? 0 : l; int si = T[ls[rr]].siz - T[ls[rl]].siz; int mid = (l + r) >> 1; if(si >= k) return Query(ls[rl], ls[rr], k, l, mid); else return Query(rs[rl], rs[rr], k - si, mid + 1, r); } int main() { // freopen("a.in", "r", stdin); // freopen("b.out", "w", stdout); N = read(); M = read(); for(int i = 1; i <= N - 1; i++) { int x = read(), y = read(); v[x].push_back(y); v[y].push_back(x); } dfs1(1, 0); dfs2(1, 1); for(int i = 1; i <= M; i++) { int x = read(), y = read(), lca = LCA(x, y); Q[dfn[x]].push_back(deep[lca]); Q[dfn[y]].push_back(deep[lca]); } for(int i = 1; i <= N; i++) { for(int j = 0; j < (int)Q[i].size(); j++) { int x = Q[i][j]; ++num; Insert(root[num], root[num - 1], 1, N, x); } ID[i] = num; } int Q = read(); while(Q--) { int u = read(), k = read(); int ans = Query(root[ID[dfn[u] - 1]], root[ID[dfn[u] + siz[u] - 1]], k, 1, N); if(ans == 0 || (deep[u] - ans <= 0)) printf("0\n"); else printf("%d\n", deep[u] - ans); } return 0; } /**/
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 津津的储蓄计划 NOIp提高组2004 2020-04-01
- 【做题笔记】[NOIOJ,非NOIp原题]装箱问题 2020-02-14
- 牛客网中矩阵中的路径 2019-10-25
- CSP(noip)中的简单对拍写法 2019-10-25
- NOIP模拟day1-T1(完全背包) 2019-10-12
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash