#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ii pair<int,int>
#define ff first
#define ss second
#pragma GCC optimize("Ofase")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int maxn = 1e5 + 5, bl = sqrt(maxn);
int n, m, q, cnt, cur;
int in[maxn], out[maxn], h[maxn], par[18][maxn], id[maxn], c[maxn], ans[maxn], in_set[maxn];
vector<int> adj[maxn], euler = {0};
struct cmp
{
bool operator() (int x, int y) const
{
return in[x] < in[y];
}
};
set<int, cmp> s;
struct Q{
int l, r, id;
bool operator < (Q b) const
{
if (l / bl != b.l / bl) return l < b.l;
return (l / bl & 1) ? (r < b.r) : (r > b.r);
}
} qr[maxn];
void dfs(int x = 1, int p = 1)
{
h[x] = h[p] + 1;
in[x] = ++cnt;
id[x] = euler.size();
euler.emplace_back(x);
for (int i : adj[x]) if (i != p)
dfs(i, x),
euler.emplace_back(x);
out[x] = cnt;
}
//inline bool sub(int u, int v) /// u in subtree of v
//{
// return in[v] <= in[u] && out[u] <= out[v];
//}
//
//int lca(int u, int v)
//{
// if (h[u] > h[v]) swap(u, v);
// if (sub(v, u)) return u;
// for (int i = 17; i >= 0; i--)
// if (sub(u, par[i][v]) == 0)
// v = par[i][v];
// return par[0][v];
//}
vector<vector<ii>> st;
inline void build()
{
int sz = euler.size();
int LG = __lg(sz);
st = vector<vector<ii>>(LG + 1, vector<ii>(sz, {sz, 0}));
for (int i = 1; i < sz; i++) st[0][i] = {h[euler[i]], euler[i]};
for (int j = 1; j <= LG; j++)
for (int i = 1; i + (1 << j) - 1 < sz; i++)
st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
inline int lca(int l, int r)
{
l = id[l];
r = id[r];
if (l > r) swap(l, r);
int k = __lg(r - l + 1);
return min(st[k][l], st[k][r - (1 << k) + 1]).ss;
}
inline void add(int x)
{
x = c[x];
in_set[x]++;
if (in_set[x] == 1)
{
cur += h[x];
if (s.size() == 0) return s.emplace(x), void();
auto it = s.lower_bound(x);
if (it == s.begin())
cur -= h[lca(x, *it)];
else if (it == s.end())
cur -= h[lca(x, *prev(it))];
else
{
auto u = *it, v = *prev(it);
cur += h[lca(u, v)];
cur -= h[lca(u, x)];
cur -= h[lca(v, x)];
}
}
s.emplace(x);
}
inline void del(int x)
{
x = c[x];
in_set[x]--;
if (in_set[x] == 0)
{
cur -= h[x];
if (s.size() == 1) return s.clear(), void();
auto it = s.lower_bound(x);
if (it == s.begin())
cur += h[lca(x, *next(it))];
else if (next(it) == s.end())
cur += h[lca(x, *prev(it))];
else
{
auto u = *prev(it), v = *next(it);
cur -= h[lca(u, v)];
cur += h[lca(u, x)];
cur += h[lca(v, x)];
}
s.erase(it);
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); //cout.tie(0);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
cin >> n >> m >> q;
for (int i = 1, u, v; i < n; i++)
cin >> u >> v,
adj[u].emplace_back(v),
adj[v].emplace_back(u);
for (int i = 1; i <= m; i++)
cin >> c[i];
dfs();
build();
for (int i = 1; i <= q; i++)
cin >> qr[i].l >> qr[i].r, qr[i].id = i;
sort(qr + 1, qr + q + 1);
for (int i = 1, l = 1, r = 0; i <= q; i++)
{
auto [lx, rx, id] = qr[i];
while (r < rx) add(++r);
while (l > lx) add(--l);
while (r > rx) del(r--);
while (l < lx) del(l++);
ans[id] = cur - h[lca(*s.begin(), *s.rbegin())] + 1;
}
for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
Compilation message
tourism.cpp:6:29: error: argument to '-O' should be a non-negative integer, 'g', 's' or 'fast'
6 | #pragma GCC optimize("Ofase")
| ^
tourism.cpp:17:36: error: argument to '-O' should be a non-negative integer, 'g', 's' or 'fast'
17 | bool operator() (int x, int y) const
| ^~~~~
tourism.cpp:27:27: error: argument to '-O' should be a non-negative integer, 'g', 's' or 'fast'
27 | bool operator < (Q b) const
| ^~~~~
tourism.cpp:34:30: error: argument to '-O' should be a non-negative integer, 'g', 's' or 'fast'
34 | void dfs(int x = 1, int p = 1)
| ^
tourism.cpp:63:19: error: argument to '-O' should be a non-negative integer, 'g', 's' or 'fast'
63 | inline void build()
| ^
tourism.cpp:74:28: error: argument to '-O' should be a non-negative integer, 'g', 's' or 'fast'
74 | inline int lca(int l, int r)
| ^
tourism.cpp:83:22: error: argument to '-O' should be a non-negative integer, 'g', 's' or 'fast'
83 | inline void add(int x)
| ^
tourism.cpp:107:22: error: argument to '-O' should be a non-negative integer, 'g', 's' or 'fast'
107 | inline void del(int x)
| ^
tourism.cpp:132:13: error: argument to '-O' should be a non-negative integer, 'g', 's' or 'fast'
132 | signed main()
| ^
