#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int ll; typedef pair P; int n; vector g[100000]; int d[100000]; int p[17][100000]; bool used[100000]; void dfs0(int x){ used[x]=1; for(auto y:g[x]){ if(!used[y]){ d[y]=d[x]+1; p[0][y]=x; dfs0(y); } } } ll ct[100000]; void dfs(int x){ used[x]=1; for(auto y:g[x]){ if(!used[y]){ dfs(y); ct[x]+=ct[y]; } } } int lca(int a, int b){ if(d[a]>d[b]) swap(a, b); int a1=a, b1=b; int dd=d[b]-d[a], i=0; while(dd>0){ if(dd%2==1){ b1=p[i][b1]; } dd/=2; i++; } if(a1==b1) return a1; for(int i=16; i>=0; i--){ if(p[i][a1]!=p[i][b1]){ a1=p[i][a1], b1=p[i][b1]; } } return p[0][a1]; } int main() { cin>>n; for(int i=0; i>u>>v; u--; v--; g[u].push_back(v); g[v].push_back(u); } dfs0(0); for(int i=1; i<17; i++){ for(int x=0; x>q; int v[100000]; for(int t=0; t>a>>b; a--; b--; int c=lca(a, b); ct[a]++; ct[b]++; if(c>0){ ct[p[0][c]]-=2; } v[t]=c; } fill(used, used+n, 0); dfs(0); for(int i=0; i