/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10;
struct query
{
int l, r, idx;
} task[maxn];
int n, m, c[maxn], q;
vector < int > adj[maxn];
void input()
{
cin >> n >> m >> q;
for (int i = 1; i < n; i ++)
{
int v, u;
cin >> v >> u;
adj[v].push_back(u);
adj[u].push_back(v);
}
for (int i = 1; i <= m; i ++)
{
cin >> c[i];
}
for (int i = 1; i <= q; i ++)
{
cin >> task[i].l >> task[i].r;
task[i].idx = i;
}
}
int depth[maxn], tin[maxn], tout[maxn];
int occ[2 * maxn], rev[2 * maxn], timer;
int sub[maxn], heavy[maxn];
void euler(int v = 1, int p = - 1)
{
occ[++ timer] = v;
tin[v] = timer;
rev[timer] = v;
sub[v] = 1;
heavy[v] = -1;
for (int u : adj[v])
{
if (u == p)
continue;
depth[u] = depth[v] + 1;
euler(u, v);
if (heavy[v] == -1 || sub[u] > sub[heavy[v]])
heavy[v] = u;
sub[v] += sub[u];
occ[++ timer] = v;
}
tout[v] = timer;
}
const int maxlog = 20;
int lg[2 * maxn], dp[maxlog][2 * maxn];
void sparse_table()
{
for (int i = 1; i <= timer; i ++)
{
lg[i] = lg[i / 2] + 1;
dp[0][i] = occ[i];
}
for (int j = 1; j < lg[timer]; j ++)
for (int i = 1; i <= timer - (1 << j); i ++)
{
dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
if (depth[dp[j - 1][i]] < depth[dp[j][i]])
dp[j][i] = dp[j - 1][i];
}
}
int get_lca(int v, int u)
{
int l = tin[v], r = tin[u];
if (l > r)
swap(l, r);
int len = lg[r - l + 1] - 1;
int lca = dp[len][r - (1 << len) + 1];
if (depth[dp[len][l]] < depth[lca])
lca = dp[len][l];
return lca;
}
int get_distance(int v, int u)
{
return depth[v] + depth[u] - 2 * depth[get_lca(v, u)];
}
struct interval
{
int left, right, value;
interval(int _left = 0, int _right = 0, int _value = 0)
{
left = _left;
right = _right;
value = _value;
}
bool operator < (const interval seg) const
{
if (left == seg.left)
{
/// values cannot be the same
return value > seg.value;
}
else
return left < seg.left;
}
};
struct chain
{
int top, left, right;
set < interval > act;
} st[maxn];
int ch_idx[maxn], ch_cnt, ord[maxn], last, ch_pos[maxn];
void hld(int v = 1, int p = -1)
{
///cout << v << " : " << p << endl;
ch_idx[v] = ch_cnt;
ord[++ last] = v;
ch_pos[v] = last;
st[ch_idx[v]].right = last;
if (heavy[v] != -1)
hld(heavy[v], v);
for (int u : adj[v])
{
if (u == p || u == heavy[v])
continue;
ch_cnt ++;
st[ch_cnt].top = v;
st[ch_cnt].left = last + 1;
st[ch_cnt].right = last + 1;
hld(u, v);
}
}
void decompose()
{
ch_idx[1] = 1;
ch_cnt = 1;
ch_pos[1] = 1;
st[ch_cnt].left = st[ch_cnt].right = 1;
st[ch_cnt].top = 0;
hld();
/**cout << ch_cnt << endl;
for (int i = 1; i <= ch_cnt; i ++)
cout << st[i].left << " " << st[i].right << endl;
for (int i = 1; i <= n; i ++)
cout << ord[i] << " ";
cout << endl;*/
}
int fen[maxn];
void update(int v, int val)
{
for (int i = v; i <= m; i += (i & -i))
fen[i] += val;
}
int query_sum(int v)
{
int s = 0;
for (int i = v; i > 0; i -= (i & -i))
s += fen[i];
return s;
}
void write_on_chain(int idx, int left, int right, int val)
{
interval seg(left, right, val);
st[idx].act.insert(seg);
set < interval > :: iterator it, bef, aft;
it = st[idx].act.find(seg);
update(val, right - left + 1);
///cout << "write on chain " << val << " " << left << " " << right << endl;
if (it != st[idx].act.begin())
{
bef = prev(it);
assert(bef -> left <= left);
if (bef -> left <= left && bef -> right >= right)
{
update(bef -> value, - (right - left + 1));
interval lf_split(bef -> left, left - 1, bef -> value);
interval rf_split(right + 1, bef -> right, bef -> value);
st[idx].act.erase(bef);
if (lf_split.left <= lf_split.right)
st[idx].act.insert(lf_split);
if (rf_split.left <= rf_split.right)
st[idx].act.insert(rf_split);
}
else if (bef -> right >= left)
{
update(bef -> value, - (bef -> right - left + 1));
interval new_bef(bef -> left, left - 1, bef -> value);
st[idx].act.erase(bef);
if (new_bef.left <= new_bef.right)
st[idx].act.insert(new_bef);
}
}
it = st[idx].act.find(seg);
if (next(it) != st[idx].act.end())
{
aft = next(it);
if (aft -> right <= right)
{
update(aft -> value, - (aft -> right - aft -> left + 1));
st[idx].act.erase(aft);
}
else if (aft -> left <= right)
{
update(aft -> value, - (right - aft -> left + 1));
interval new_aft(right + 1, aft -> right, aft -> value);
st[idx].act.erase(aft);
if (new_aft.left <= new_aft.right)
st[idx].act.insert(new_aft);
}
}
}
void write_on_path(int v, int p, int val)
{
///cout << "write on path " << v << " " << p << endl;
while(ch_idx[v] != ch_idx[p])
{
write_on_chain(ch_idx[v], st[ch_idx[v]].left, ch_pos[v], val);
v = st[ch_idx[v]].top;
}
if (ch_pos[p] < ch_pos[v])
write_on_chain(ch_idx[v], ch_pos[p] + 1, ch_pos[v], val);
}
vector < query > ask[maxn];
int res[maxn];
void queries()
{
for (int i = 1; i <= q; i ++)
ask[task[i].l].push_back(task[i]);
for (int i = m; i > 0; i --)
{
if (i != m)
{
int v = c[i], u = c[i + 1];
int lca = get_lca(v, u);
write_on_path(v, lca, i);
write_on_path(u, lca, i);
}
/**cout << "step " << i << endl;
for (int j = 1; j <= m; j ++)
cout << query_sum(j) - query_sum(j - 1) << " ";
cout << endl;*/
for (query cur : ask[i])
{
res[cur.idx] = query_sum(cur.r - 1) + 1;
}
}
for (int i = 1; i <= q; i ++)
cout << res[i] << endl;
}
void solve()
{
input();
euler();
sparse_table();
decompose();
queries();
}
int main()
{
speed();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 2 |
Correct |
3 ms |
18776 KB |
Output is correct |
| 3 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 2 |
Correct |
3 ms |
18776 KB |
Output is correct |
| 3 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 3 |
Correct |
3 ms |
16984 KB |
Output is correct |
| 4 |
Incorrect |
89 ms |
41736 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 2 |
Incorrect |
114 ms |
34980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 3 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 4 |
Incorrect |
300 ms |
39752 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 2 |
Correct |
3 ms |
18776 KB |
Output is correct |
| 3 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
