A
直接往右推，如果当前点的和不够 (0 o i-1) 的和，那么就是 (No)
B
答案必然是中位数的那个区间里面，排序之后偶数就两个减，反之就是 (1)
C
(WA) 了好几发
先找到[1,n] 的次大值，然后找到最大值在左边还是右边
区间次大值是/不是次大值是有单调性的，二分
D
二分，对于每个数都减 (mid) ，取前缀 (min)，然后扫一下看是不是有区间和大于 (0)的
注意是 (>0)，(s[i]>0) 也得算，因为这个 (WA) 了几下
E
赛时没有过
关键点是 (wle 50)，所以把每个点拆出来 (50) 个入点，一个出点
对于 ((u,v,w)) 连上 ((u,(v+w),0)) 然后连每个 (((u+i),v,(w+i)^2))
最后来一个 (dij)，这个和美食节那个有点像，需要观察到边权的特殊性
F
每个点链顶打个 (tag)，底打 (tag)，在转移儿子打 (tag)
统计的时候转移儿子的贡献减掉
实现并不好写
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define For(i,a,b) for(register int i=a;i<=b;++i)
#define Down(i,a,b) for(register int i=a;i>=b;i--)
#define reg register
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
inline void swap(int &x,int &y){int t=x; x=y; y=t; return ;}
namespace yspm{
inline int read(){
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=3e5+10;
struct node{int to,nxt;}e[N<<1];
int head[N],cnt,dfn[N],tim,dep[N],fa[N],top[N],n,sz[N],son[N];
inline void add(int x,int y){
e[++cnt].to=y; e[cnt].nxt=head[x];
return head[x]=cnt,void();
}
inline void dfs1(int x,int y){ fa[x]=y; dep[x]=dep[y]+1; sz[x]=1;
for(reg int i=head[x];i;i=e[i].nxt){
int t=e[i].to; if(t==y) continue;
dfs1(t,x); sz[x]+=sz[t]; if(sz[t]>sz[son[x]]) son[x]=t;
} return ;
}
inline void dfs2(int x,int y){
top[x]=y; dfn[x]=++tim; if(son[x]) dfs2(son[x],y); else return ;
for(reg int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa[x]&&e[i].to!=son[x]) dfs2(e[i].to,e[i].to);
return ;
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
else y=fa[top[y]];
} if(dep[x]>dep[y]) swap(x,y);
return x;
}
vector<pair<int,int> >rd[N];
int s[N],ans,m,F[N],num[N];
inline int find(int x){return F[x]==x?F[x]:F[x]=find(F[x]);}
map<pair<int,int>,int>mp;
inline void solve(int x){
for(reg int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa[x]) solve(e[i].to),s[x]+=s[e[i].to];
mp.clear(); int tot=0;
for(auto p:rd[x]){
int px=p.first,py=p.second;
px=find(px),py=find(py); if(px==x) px=0; else --s[px];
if(py==x) py=0; else --s[py]; if(px>py) swap(px,py);
if(px) ans+=tot-num[px]-num[py]+mp[make_pair(px,py)];
else if(py) ans+=tot-num[py]; else ans+=tot;
// cout<<p.first<<" "<<p.second<<endl;
++tot; ++num[px]; ++num[py]; ++mp[make_pair(px,py)];
// cout<<px<<" ---"<<num[px]<<endl;
} ans+=s[x]*tot;
for(reg int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa[x]) F[e[i].to]=x,ans-=s[e[i].to]*num[e[i].to];
// cout<<x<<" "<<ans<<endl;
return ;
}
signed main(){
freopen("1.in","r",stdin);
n=read(); for(reg int i=1,u,v;i<n;++i) F[i]=i,u=read(),v=read(),add(u,v),add(v,u); F[n]=n; dfs1(1,0); dfs2(1,1);
m=read(); for(reg int i=1,x,y,l;i<=m;++i) ++s[x=read()],++s[y=read()],s[l=lca(x,y)]-=2,rd[l].push_back(make_pair(x,y));
solve(1); printf("%lld
",ans);
return 0;
}
}
signed main(){return yspm::main();}