SPOJ COT2 - Count on a tree II(树上莫队)
2018-06-27 09:42:55来源:博客园 阅读 ()
题目描述
给定一个n个节点的树,每个节点表示一个整数,问u到v的路径上有多少个不同的整数。
输入格式
第一行有两个整数n和m(n=40000,m=100000)。
第二行有n个整数。第i个整数表示第i个节点表示的整数。
在接下来的n-1行中,每行包含两个整数u v,描述一条边(u,v)。
在接下来的m行中,每一行包含两个整数u v,询问u到v的路径上有多少个不同的整数。
输出格式
对于每个询问,输出结果。 贡献者:つるまる
题目描述
You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.
We will ask you to perform the following operation:
- u v : ask for how many different integers that represent the weight of nodes there are on the path from u to v.
输入输出格式
输入格式:
In the first line there are two integers N and M. (N <= 40000, M <= 100000)
In the second line there are N integers. The i-th integer denotes the weight of the i-th node.
In the next N-1 lines, each line contains two integers u v, which describes an edge (u, v).
In the next M lines, each line contains two integers u v, which means an operation asking for how many different integers that represent the weight of nodes there are on the path from u to v.
输出格式:
For each operation, print its result.
输入输出样例
8 2 105 2 9 3 8 5 7 7 1 2 1 3 1 4 3 5 3 6 3 7 4 8 2 5 7 8
4 4
SDOI 2018因为没学过树上莫队惨遭爆零,
不过这玩意儿确实定好玩的。
首先建出欧拉序来,然后对于每个询问,分两种情况讨论。
这里就不展开讲了,
#include<cstdio> #include<cmath> #include<algorithm> #include<vector> //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++) char buf[1 << 21], *p1 = buf, *p2 = buf; using namespace std; const int MAXN = 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, Q; int belong[MAXN], block; struct Query { int l, r, ID, lca, ans; bool operator < (const Query &rhs) const{ return belong[l] == belong[rhs.l] ? r < rhs.r : belong[l] < belong[rhs.l]; // return belong[l] < belong[rhs.l]; } }q[MAXN]; vector<int>v[MAXN]; int a[MAXN], date[MAXN]; void Discretization() { sort(date + 1, date + N + 1); int num = unique(date + 1, date + N + 1) - date - 1; for(int i = 1; i <= N; i++) a[i] = lower_bound(date + 1, date + num + 1, a[i]) - date; } int deep[MAXN], top[MAXN], fa[MAXN], siz[MAXN], son[MAXN], st[MAXN], ed[MAXN], pot[MAXN], tot; void dfs1(int x, int _fa) { fa[x] = _fa; siz[x] = 1; st[x] = ++ tot; pot[tot] = x; for(int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if(deep[to]) continue; deep[to] = deep[x] + 1; dfs1(to, x); siz[x] += siz[to]; if(siz[to] > siz[son[x]]) son[x] = to; } ed[x] = ++tot; pot[tot] = x; } void dfs2(int x, int topfa) { top[x] = topfa; if(!son[x]) return ; dfs2(son[x], topfa); for(int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if(top[to]) continue; dfs2(to, to); } } int GetLca(int x, int y) { while(top[x] != top[y]) { if(deep[top[x]] < deep[top[y]]) swap(x, y); x = fa[top[x]]; } return deep[x] < deep[y] ? x : y; } void DealAsk() { for(int i = 1; i <= Q; i++) { int x = read(), y = read(); if(st[x] > st[y]) swap(x, y); int _lca = GetLca(x, y); q[i].ID = i; if(_lca == x) q[i].l = st[x], q[i]. r = st[y]; else q[i].l = ed[x], q[i].r = st[y], q[i].lca = _lca; } } int Ans, out[MAXN], used[MAXN], happen[MAXN]; void add(int x) { if(++happen[x] == 1) Ans++; } void delet(int x) { if(--happen[x] == 0) Ans--; } void Add(int x) { used[x] ? delet(a[x]) : add(a[x]); used[x] ^= 1; } void Mo() { sort(q + 1, q + Q + 1); int l = 1, r = 0, fuck = 0; for(int i = 1; i <= Q; i++) { while(l < q[i].l) Add(pot[l]), l++, fuck++; while(l > q[i].l) l--, Add(pot[l]), fuck++; while(r < q[i].r) r++, Add(pot[r]), fuck++; while(r > q[i].r) Add(pot[r]), r--, fuck++; if(q[i].lca) Add(q[i].lca); q[i].ans = Ans; if(q[i].lca) Add(q[i].lca); } for(int i = 1; i <= Q; i++) out[q[i].ID] = q[i].ans; for(int i = 1; i <= Q; i++) printf("%d\n", out[i]); } int main() { N = read(); Q = read(); //block = 1.5 * sqrt(2 * N) + 1; //block = pow(N, 0.66666666666); block = sqrt(N); for(int i = 1; i <= N; i++) a[i] = date[i] = read(); for(int i = 1; i <= N * 2; i++) belong[i] = i / block + 1; Discretization(); for(int i = 1; i <= N - 1; i++) { int x = read(), y = read(); v[x].push_back(y); v[y].push_back(x); } deep[1] = 1; dfs1(1, 0); dfs2(1, 1); /* for(int i = 1; i <= N; i++) for(int j = 1; j <= i - 1; j++) printf("%d %d %d\n", i, j, GetLca(i, j));*/ DealAsk(); Mo(); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- CodeForces Gym 100213F Counterfeit Money 2020-02-13
- CountingSort(计数排序)原理及C++代码实现 2020-01-14
- 【题解】CF161B Discounts 2019-11-11
- constexpr函数"QAlgorithmsPrivate::qt_builtin_po 2019-04-30
- 1004 Counting Leaves (30 分)(树的遍历) 2018-12-09
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