#include<bits/stdc++.h> using namespace std; #define foru(i,a,b) for(int i=(a); i<=(b); ++i) #define ford(i,a,b) for(int i=(a); i>=(b); --i) #define rep(i,a) for(int i=0; i<(a); ++i) #define sz(a) (int)(a).size() #define all(a) (a).begin(),(a).end() #define bit(s,i) (((s)>>(i))&1) #define ii pair<int,int> #define vi vector<int> #define vii vector<ii> #define fi first #define se second #define ll long long #define eb emplace_back #define pb push_back #define __builtin_popcount __builtin_popcountll #define _ << " " << template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;} template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;} const int N=101010; const int B=2000; const int LG=17; int n,m,q,c[N],ans[N],h[N]; int tin[N],tout[N],tour[N],par[N],minH[LG+1][N],tim; vi adj[N]; struct Query{ int l,r,id; }; vector<Query> que[N]; void dfs(int u, int p=-1){ tin[u]=++tim; tour[tim]=u; for(int v:adj[u]) if(v!=p){ h[v]=h[u]+1; par[v]=u; dfs(v,u); } tout[u]=tim; } void buildLCA(){ foru(i,1,n){ minH[0][i]=tour[i]; } for(int i=1; 1<<i <= n; ++i){ for(int j=1; j+(1<<i)-1 <= n; ++j){ if(h[minH[i-1][j]] < h[minH[i-1][j+(1<<(i-1))]]){ minH[i][j]=minH[i-1][j]; } else{ minH[i][j]=minH[i-1][j+(1<<(i-1))]; } } } } int get(int l, int r){ int lg=__lg(r-l+1); if(h[minH[lg][l]] < h[minH[lg][r-(1<<lg)+1]]) return minH[lg][l]; return minH[lg][r-(1<<lg)+1]; } int lca(int u, int v){ if(u==v) return u; if(tin[u]>tin[v]) swap(u,v); return par[get(tin[u]+1,tin[v])]; } int dist(int u, int v){ return h[u]+h[v]-2*h[lca(u,v)]; } int nxt[N],prv[N],mostL,mostR,cost; int turn[N]; void del(int x){ int pos=tin[c[x]]; --turn[pos]; if(turn[pos]==0){ cost-=dist(tour[mostL], tour[mostR]); int l=prv[pos], r=nxt[pos]; if(l!=-1) cost-=dist(tour[l], tour[pos]), nxt[l]=r; if(r!=-1) cost-=dist(tour[pos],tour[r]), prv[r]=l; if(l!=-1 && r!=-1) cost+=dist(tour[l],tour[r]); if(nxt[l]==-1) mostR=l; if(prv[r]==-1) mostL=r; cost+=dist(tour[mostL],tour[mostR]); } } vector<pair<int&, int>> vt; void delRoll(int x){ int pos=tin[c[x]]; vt.eb(turn[pos],turn[pos]); --turn[pos]; if(turn[pos]==0){ vt.eb(cost,cost); cost-=dist(tour[mostL], tour[mostR]); int l=prv[pos], r=nxt[pos]; if(l!=-1) cost-=dist(tour[l], tour[pos]), vt.eb(nxt[l],nxt[l]), nxt[l]=r; if(r!=-1) cost-=dist(tour[pos],tour[r]), vt.eb(prv[r],prv[r]), prv[r]=l; if(l!=-1 && r!=-1) cost+=dist(tour[l],tour[r]); if(nxt[l]==-1) vt.eb(mostR,mostR), mostR=l; if(prv[r]==-1) vt.eb(mostL,mostL), mostL=r; cost+=dist(tour[mostL],tour[mostR]); } } void roll(){ while(vt.size()){ vt.back().fi=vt.back().se; vt.pop_back(); } } void process(){ foru(i,0,n/B){ sort(all(que[i]),[](Query x, Query y){return x.r>y.r;}); cost=0; foru(j,1,n) turn[j]=0; foru(j,i*B,m-1) turn[tin[c[j]]]++; int cur=-1; foru(j,1,n) if(turn[j]>0){ if(cur==-1) mostL=j; prv[j]=cur; cur=j; } cur=-1; ford(j,n,1) if(turn[j]>0){ if(cur==-1) mostR=j; nxt[j]=cur; cur=j; if(nxt[j]!=-1){ cost+=dist(tour[j],tour[nxt[j]]); } } cost+=dist(tour[mostL],tour[mostR]); int r=m-1; for(auto j:que[i]){ while(r>j.r) del(r--); int l=i*B; while(l<j.l) delRoll(l++); ans[j.id]=cost; roll(); } } } void solve(){ cin>>n>>m>>q; rep(i,n-1){ int u,v; cin>>u>>v; adj[u].eb(v); adj[v].eb(u); } rep(i,m) cin>>c[i]; rep(i,q){ int l,r; cin>>l>>r; --l, --r; que[l/B].pb({l,r,i}); } dfs(1); buildLCA(); process(); rep(i,q) cout<<ans[i]/2+1<<'\n'; } int32_t main(){ #define task "test" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin.tie(0)->sync_with_stdio(0); int tc=1; //cin>>tc; foru(i,1,tc){ solve(); } }

tourism.cpp: In function 'int32_t main()':
tourism.cpp:188:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:189:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~