This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
const ll maxn=100005;
vector <ll> A[maxn];
vector <pll> L[maxn];
ll n, m, q, St[maxn*4], bit[maxn], c[maxn], ans[maxn];
ll Time, tin[maxn], h[maxn], pa[maxn], dep[maxn], child[maxn], big[maxn];
void update(ll i, ll val)
{
// cout << i << " " << val << "\n";
for (; i<=n; i+=i&(-i))
bit[i]+=val;
}
ll query(ll l, ll r)
{
ll ans=0; l--;
for (; r; r-=r&(-r))
ans+=bit[r];
for (; l; l-=l&(-l))
ans-=bit[l];
return ans;
}
void update(ll i, ll Start, ll End, ll l, ll r, ll val)
{
if (Start>r || End<l)
return;
// cout << i << " " << St[i] << " " << Start << " " << End << " " << l << " " << r << " " << val << "\n";
if (Start>=l && End<=r && St[i]!=-1)
{
if (St[i]) update(St[i], -(End-Start+1));
update(val, End-Start+1);
St[i]=val;
return;
}
if (St[i]!=-1) St[i*2]=St[i*2+1]=St[i];
ll mid=(Start+End)/2;
if (mid>=l) update(i*2, Start, mid, l, r, val);
if (mid+1<=r) update(i*2+1, mid+1, End, l, r, val);
if (St[i*2]==St[i*2+1]) St[i]=St[i*2];
else St[i]=-1;
}
void dfs(ll u)
{
child[u]=1;
for (ll v:A[u])
if (v!=pa[u])
{
dep[v]=dep[u]+1, pa[v]=u;
dfs(v), child[u]+=child[v];
if (child[v]>child[big[u]])
big[u]=v;
}
}
void dfs2(ll u)
{
tin[u]=++Time;
if (u==big[pa[u]])
h[u]=h[pa[u]];
else h[u]=u;
if (big[u]) dfs2(big[u]);
for (ll v:A[u])
if (v!=pa[u] && v!=big[u])
dfs2(v);
}
void update(ll u, ll v, ll val)
{
for (; h[u]!=h[v]; u=pa[h[u]])
{
if (dep[h[u]]<dep[h[v]])
swap(u, v);
update(1, 1, n, tin[h[u]], tin[u], val);
}
if (dep[u]<dep[v]) swap(u, v);
update(1, 1, n, tin[v], tin[u], val);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
for (ll i=1; i<n; i++)
{
ll u, v; cin >> u >> v;
A[u].pb(v); A[v].pb(u);
}
dfs(1); dfs2(1);
for (ll i=1; i<=m; i++)
cin >> c[i];
for (ll i=1; i<=q; i++)
{
ll l, r; cin >> l >> r;
L[r].pb({l, i});
}
for (ll i=1; i<=m; i++)
{
if (i>1) update(c[i-1], c[i], i-1);
update(c[i], c[i], i);
for (auto &[l, idx]:L[i])
ans[idx]=query(l, i);
}
for (ll i=1; i<=q; i++)
cout << ans[i] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |