| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1303319 | wonderful | Tourism (JOI23_tourism) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
vector <int> z[1000005];
int sta[1000005],fin[1000005],euler[1000005];
int high[1000005];
int tour;
int st[300001][21];
int logarit[1000005];
int l,r;
void dfs(int i,int par){
tour++;
sta[i]=tour;
euler[tour]=i;
for (auto p:z[i]){
if (p==par){
continue;
}
high[p]=high[i]+1;
dfs(p,i);
tour++;
euler[tour]=i;
}
tour++;
fin[i]=tour;
euler[tour]=i;
}
void buildst(){
for (int i=1;i<=tour;i++){
st[i][0]=euler[i];
}
for (int j=1;(1<<j)<=tour;j++){
for (int i=1;i+(1<<j)-1<=tour;i++){
int l=st[i][j-1];
int r=st[i+(1<<(j-1))][j-1];
if (high[l]<high[r]){
st[i][j]=l;
}else{
st[i][j]=r;
}
}
}
}
int lca(int x,int y){
int l=min(sta[x],sta[y]);
int r=max(sta[x],sta[y]);
int j=logarit[r-l+1];
int idx1=st[l][j];
int idx2=st[r-(1<<j)+1][j];
if (high[idx1]<high[idx2]){
return idx1;
}else{
return idx2;
}
}
int block;
int t[1000005];
struct node{
int l,r,id;
};
node q[1000005];
bool cmp(node a,node b){
int blocka=a.l/block;
int blockb=b.l/block;
if (blocka!=blockb){
return blocka<blockb;
}
return a.r<b.r;
}
struct compare{
bool operator()(int a,int b){
return sta[a]>sta[b];
}
};
multiset<int,compare> s;
int sum=0;
int res[1000005];
int cal(int x,int y){
return high[x]+high[y]-2*high[lca(x,y)];
}
void add(int x){
x=t[x];
if (!s.size()){
s.insert(x);
return;
}
auto it=s.lower_bound(x);
if (it==s.begin()){
auto it1=s.rbegin();
sum-=cal(*it1,*it);
sum+=cal(*it1,x);
sum+=cal(*it,x);
}else if (it==s.end()){
--it;
auto it1=s.begin();
sum-=cal(*it1,*it);
sum+=cal(*it1,x);
sum+=cal(*it,x);
}else{
auto it1=it;
--it1;
sum-=cal(*it1,*it);
sum+=cal(*it1,x);
sum+=cal(*it,x);
}
s.insert(x);
}
void del(int x){
x=t[x];
auto it=s.lower_bound(x);
if (s.size()==1){
s.erase(it);
return;
}
auto pre=s.end();
--pre;
if (it==s.begin()){
auto it1=s.rbegin();
auto it2=it;
++it2;
sum+=cal(*it1,*it2);
sum-=cal(*it1,*it);
sum-=cal(*it2,*it);
}else if (it==pre){
auto it1=s.begin();
auto it2=it;
--it2;
sum+=cal(*it1,*it2);
sum-=cal(*it1,*it);
sum-=cal(*it2,*it);
}else{
auto it1=it;
auto it2=it;
--it2;
it1++;
sum+=cal(*it1,*it2);
sum-=cal(*it1,*it);
sum-=cal(*it2,*it);
}
s.erase(it);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int a,b,c;
cin >> a >> b >> c;
for (int i=1;i<a;i++){
int x,y;
cin >> x >> y;
z[x].push_back(y);
z[y].push_back(x);
}
logarit[2]=1;
for (int i=3;i<=1e6;i++){
logarit[i]=logarit[i/2]+1;
}
dfs(1,1);
buildst();
block=sqrt(b);
for (int i=1;i<=b;i++){
cin >> t[i];
}
for (int i=1;i<=c;i++){
int x,y;
cin >> x >> y;
q[i]={x,y,i};
}
sort(q+1,q+1+c,cmp);
l=q[1].l;
r=q[1].r;
for (int i=l;i<=r;i++){
add(i);
}
res[q[1].id]=sum/2+1;
// for (int i=1;i<=c;i++){
// cout << q[i].id << " ";
// }
// cout << "\n";
// cerr << "\n";
// cerr << 1 << " " << q[1].id << "\n";
for (int i=2;i<=c;i++){
while (l>q[i].l){
l--;
add(l);
}
while (r<q[i].r){
r++;
add(r);
}
while (l<q[i].l){
del(l);
l++;
}
while (r>q[i].r){
del(r);
r--;
}
res[q[i].id]=sum/2+1;
// cerr << i << " " << q[i].id << " " << s.size() << " " << *s.begin() << "\n";
}
for (int i=1;i<=c;i++){
cout << res[i] << "\n";
}
return 0;
}