QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#416031 | #5403. 树数术 | fairyqq28 | 0 | 0ms | 0kb | C++14 | 3.7kb | 2024-05-21 14:59:39 | 2024-05-21 14:59:41 |
answer
// #pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define rep(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define per(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define ls (u<<1)
#define rs (u<<1|1)
using namespace std;
typedef pair<int, int> pii;
const int N = 700010;
char buf[1<<20], *p1, *p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<20, stdin), p1==p2)?0:*p1++)
int read(){
int ret = 0; char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) ret = (ret<<1)+(ret<<3)+(c^48), c = getchar();
return ret;
}
int stk[15], top;
void print(int x){
do stk[++top] = x % 10, x /= 10; while(x);
while(top) putchar(stk[top] ^ 48), top--;
putchar('\n');
}
int a[N], dep[N];
int lca(int x, int y);
namespace TREE{
int lc[N<<2];
vector<int> t[N<<2];
void build(int u, int l, int r){
if(l == r) {t[u] = {a[l]}, lc[u] = a[l]; return;}
int mid = (l + r) >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
t[u] = t[ls];
int tmp = lca(lc[ls], t[rs].front());
for(int &i : t[rs]) if(dep[i] <= dep[tmp]) t[u].push_back(i);
lc[u] = lca(lc[ls], lc[rs]);
}
pii calc(int u, int id){
// if(!~id) printf("%d %d %d\n", u, id, t[u].size());
if(!~id) return make_pair(lc[u], t[u].size());
id = lca(id, t[u].front());
int l = 0, r = t[u].size() - 1, ret = t[u].size();
while(l <= r){
int mid = (l + r) >> 1;
if(dep[t[u][mid]] <= dep[id]) ret = mid, r = mid - 1;
else l = mid + 1;
}
// printf("%d %d %d\n", u, id, t[u].size() - ret);
return make_pair(lca(id, lc[u]), t[u].size() - ret);
}
// return pair<int, int> (the id of min dep, cnt)
pii query(int u, int l, int r, int x, int y, int id){
// if(x <= l && r <= y) printf("query: %d %d %d\n", u, l, r);
if(x <= l && r <= y) return calc(u, id);
// if(l == r) return calc(u, id);
int cnt = 0, mid = (l + r) >> 1;
if(x <= mid){
pii tmp = query(ls, l, mid, x, y, id);
id = tmp.first; cnt += tmp.second;
}
if(y > mid){
pii tmp = query(rs, mid + 1, r, x, y, id);
id = tmp.first; cnt += tmp.second;
}
return make_pair(id, cnt);
}
}
using TREE::build; using TREE::query;
int st[N<<1][21], blg[N], tot;
vector<int> e[N];
void dfs(int x, int F){
dep[x] = dep[F] + 1;
st[++tot][0] = x; blg[x] = tot;
for(int &y : e[x]) if(y ^ F) dfs(y, x), st[++tot][0] = x;
}
void st_init(){
rep(j, 1, 20) rep(i, 1, tot - (1<<j) + 1)
if(dep[st[i][j-1]] < dep[st[i+(1<<(j-1))][j-1]])
st[i][j] = st[i][j-1];
else st[i][j] = st[i+(1<<(j-1))][j-1];
}
int lca(int x, int y){
x = blg[x], y = blg[y];
if(x > y) swap(x, y);
int t = __lg(y - x + 1);
if(dep[st[x][t]] < dep[st[y-(1<<t)+1][t]]) return st[x][t];
else return st[y-(1<<t)+1][t];
}
int n, m, q;
int main(){
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
n = read(), m = read(), q = read();
rep(i, 1, n - 1){
int x = read(), y = read();
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1, 0);
st_init();
rep(i, 1, m) a[i] = read();
build(1, 1, m);
while(q--){
int k = read(), id = -1, ans = 0;
rep(i, 1, k){
int x = read(); int y = read();
pii tmp = query(1, 1, m, x, y, id);
id = tmp.first; ans += tmp.second;
}
print(ans);
}
// cerr << "total time: " << (clock() * 1000 / CLOCKS_PER_SEC) << "ms\n";
return 0;
}
详细
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
699990 699995 233333 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...
output:
result:
Subtask #2:
score: 0
Dangerous Syscalls
Test #2:
score: 0
Dangerous Syscalls
input:
699992 699994 699992 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 29 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 40 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 ...
output:
result:
Subtask #3:
score: 0
Dangerous Syscalls
Test #3:
score: 0
Dangerous Syscalls
input:
99998 99993 33333 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 24 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 41 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 49 ...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%