#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
struct FT{
vector<int> bit;
int n;
FT(int ns){
n = ns;
bit.resize(n + 1);
}
void upd(int v, int k){
while (v <= n){
bit[v] += k;
v |= (v + 1);
}
}
int get(int v){
int out = 0;
while (v > 0){
out += bit[v];
v = (v & (v + 1)) - 1;
}
return out;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, q; cin>>n>>m>>q;
vector<int> g[n + 1];
for (int i = 1; i < n; i++){
int a, b; cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
vector<int> c(m + 1);
for (int i = 1; i <= m; i++){
cin>>c[i];
}
vector<int> pos(n + 1), sz(n + 1), p(n + 1), heavy(n + 1), head(n + 1), d(n + 1);
function<void(int, int)> dfs = [&](int v, int pr){
p[v] = pr; sz[v] = 1;
for (int i: g[v]){
if (i == pr) continue;
d[i] = d[v] + 1;
dfs(i, v);
if (sz[i] > sz[heavy[v]]){
heavy[v] = i;
}
sz[v] += sz[i];
}
};
dfs(1, 0);
int timer = 0;
function<void(int, int, int)> dfs_hld = [&](int v, int pr, int k){
pos[v] = ++timer;
head[v] = k;
if (!heavy[v]) return;
dfs_hld(heavy[v], v, k);
for (int i: g[v]){
if (i == pr || i == heavy[v]){
continue;
}
dfs_hld(i, v, i);
}
};
dfs_hld(1, 0, 1);
vector<pii> end[m + 1];
vector<int> out(q + 1);
for (int i = 1; i <= q; i++){
int l, r; cin>>l>>r;
if (l == r){
out[i] = 1;
continue;
}
end[l].push_back({r, i});
}
FT T(m);
set<array<int, 3>> st;
auto set = [&](int l, int r, int x){
while (!st.empty()){
auto it = st.lower_bound({l, 0, 0});
if (it == st.end() || (*it)[0] > r) break;
auto [a, b, k] = *it;
if (b <= r){
T.upd(k, -(b - a + 1));
st.erase(it);
}
else {
T.upd(k, -(r - a + 1));
st.erase(it);
st.insert({r + 1, b, k});
}
}
while (!st.empty()){
auto it = st.upper_bound({l, 0, 0}); it--;
if ((*it)[1] < l) break;
auto [a, b, k] = *it;
if (b < r){
T.upd(k, -(r - l + 1));
st.erase(it);
st.insert({a, l - 1, k});
st.insert({b + 1, r, k});
}
else {
T.upd(k, -(b - l + 1));
st.erase(it);
st.insert({a, l - 1, k});
}
}
T.upd(x, (r - l + 1));
st.insert({0, 0, 0});
st.insert({l, r, x});
auto it = st.begin();
while (it != prev(st.end())){
auto it1 = it; it1++;
auto [l1, r1, k1] = *it;
auto [l2, r2, k2] = *it;
if (l2 <= r1){
int out = 0;
while (true){
out++;
}
}
}
};
auto add = [&](int u, int v, int x){
while (head[u] != head[v]){
if (d[head[u]] > d[head[v]]){
swap(u, v);
}
set(pos[head[v]], pos[v], x);
v = p[head[v]];
}
if (d[u] > d[v]) swap(u, v);
set(pos[u] + 1, pos[v], x);
};
for (int l = m; l > 0; l--){
if (l != m){
add(c[l], c[l + 1], l);
}
for (auto [r, j]: end[l]){
out[j] = T.get(r - 1) + 1;
}
}
for (int i = 1; i <= q; i++){
cout<<out[i]<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5038 ms |
360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5038 ms |
360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5022 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5096 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5047 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5038 ms |
360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
