#include using namespace std; #define modulo 998244353 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000005 vector> order; vector L; int N,K,Q; vector dis; vector calc; vector cnt; vector C; template struct sparse_table{ const T init_value = make_pair(1000000001,1000001); vector v; int n; int sz; sparse_table(vector &x){ sz = x.size(); for(int i=0;true;i++){ if((1<sz){ n = i; break; } } v.resize(sz*n,init_value); for(int i=0;i> &E,int now,int p){ cnt[now] = C[now]; for(int i=0;i> &E,int now,int p){ if(p==-1){ calc[now] = 0; for(int i=0;i> &E,int now,int p,int d=0){ dis[now] =d; L[now] = order.size(); order.emplace_back(d,now); vector t; for(int i=0;i> &S,int u,int v){ if(u==v)return 0; int l = min(L[u],L[v]); int r = max(L[u],L[v]); int x = S.query(l,r+1).second; return dis[u]+dis[v]-2*dis[x]; } int main(){ cin>>N>>K>>Q; C.resize(N,0); vector pos(K); for(int i=0;i> E(N); for(int i=0;i> S(order); calc.resize(N); cnt.resize(N); dfs(E,0,-1); dfs2(E,0,-1); vector> Movement; for(int i=0;i350){ for(int j=0;j