#include #include using namespace std; int N; vectorG[1<<17]; int pr[17][1<<17],dep[1<<17]; void dfs(int u,int p,int d) { dep[u]=d; pr[0][u]=p; for(int v:G[u])if(v!=p)dfs(v,u,d+1); } int cnt[1<<17]; long ans; int dfs2(int u,int p) { for(int v:G[u])if(v!=p) { cnt[u]+=dfs2(v,u); } ans+=(long)cnt[u]*(cnt[u]+1)/2; return cnt[u]; } main() { cin>>N; for(int i=1;i>u>>v; u--,v--; G[u].push_back(v); G[v].push_back(u); } dfs(0,-1,0); for(int k=1;k<17;k++)for(int i=0;i>Q; for(;Q--;) { int a,b;cin>>a>>b; a--,b--; int lca; int u=a,v=b; if(dep[u]>dep[v]) { int t=u;u=v;v=t; } for(int k=0;k<17;k++)if(dep[v]-dep[u]>>k&1)v=pr[k][v]; if(u==v)lca=u; else { for(int k=17;k--;)if(pr[k][u]!=pr[k][v]) { u=pr[k][u]; v=pr[k][v]; } lca=pr[0][u]; } cnt[a]++; cnt[b]++; cnt[lca]--; if(pr[0][lca]>=0)cnt[pr[0][lca]]--; } dfs2(0,-1); cout<