SOL:
对这棵树进行树分治，求出重心到每个点的前缀和 s。 对于两个点 i, j，假设是从 i 开始走到 j，那么它们的 s 互为 相反数，且 i 的 s 是它到重心路径上最大的，j 的 s 则是最 小的。
同时维护一下最值出现的个数，即可得到将两条链拼起来的 链的 f 值。 将所有点按 s 桶排序，对于每种 s 值单独计算，因为 k 固 定，所以知道了某一项，另一项也知道，直接计数即可。
我们发现这是一个卷积，FFT就好了。
#pragma GCC optimize("-O3") #include<bits/stdc++.h> #define db double #define N 130071 const db pi=acos(-1.0); using namespace std; int D[N],L,m,son[N],all,f[N],u[N],now,aa[N],dep,h[N],ga[N],gb[N]; int A[N],B[N],C[N],anw[N],n,x,y; #define sight(x) ('0'<=x&&x<='9') inline void read(int &x){ static char c; for (c=getchar();!sight(c);c=getchar()); for (x=0;sight(c);c=getchar())x=x*10+c-48; } void write(int x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);} inline void writeln(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); } inline void writel(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); } struct com{ db r,i; com(){} com(db x,db y):r(x),i(y){} inline com operator +(com &X) {return com(r+X.r,i+X.i);} inline com operator -(com &X) {return com(r-X.r,i-X.i);} inline com operator *(com &X) {return com(r*X.r-i*X.i,i*X.r+r*X.i);} }a[N],b[N],wn,w,X,Y; inline void FFT(com* a,int n,int x){ for (int i=0;i<n;i++) if (i<D[i]) swap(a[i],a[D[i]]); for (int i=1;i<n;i<<=1) { wn.r=cos(pi/i); wn.i=x*sin(pi/i); for (int j=0;j<n;j+=(i<<1)){ w.r=1; w.i=0; for (int k=j;k<i+j;k++,w=w*wn) {X=a[k]; Y=w*a[k+i]; a[k]=X+Y; a[k+i]=X-Y;} } } if (x==-1) for (int i=0;i<n;i++) a[i].r/=n; } inline void mul(int * x,int * y,int *z,int n) { for (m=1,L=0;m<=n;m<<=1) L++; m<<=1; for (int i=0;i<m;i++) D[i]=(D[i>>1]>>1)|((i&1)<<L); for (int i=0;i<=n;i++) a[i].r=x[i],a[i].i=0,b[i].r=y[i],b[i].i=0; for (int i=n+1;i<m;i++) a[i].r=a[i].i=b[i].r=b[i].i=0; FFT(a,m,1); FFT(b,m,1); for (int i=0;i<m;i++) a[i]=a[i]*b[i]; FFT(a,m,-1); for (int i=0;i<m;i++) z[i]=(int)(a[i].r+0.2); } int fall[N<<1],net[N<<1],head[N],tot,fal[N<<1],nt[N<<1],ed; inline void add(int x,int y) { fall[++tot]=y; net[tot]=head[x]; head[x]=tot; } #define eho(x) for (int i=head[x];i;i=net[i]) #define v fall[i] inline void ad(int &x,int y) {fal[++ed]=y;nt[ed]=x;x=ed;} void fr(int x,int fa){ son[x]=1,f[x]=0; eho(x) if ((!u[v])&&v^fa) { fr(v,x); son[x]+=son[v]; if (son[v]>f[x]) f[x]=son[v]; } if (all-son[x]>f[x]) f[x]=all-son[x]; if (f[x]<f[now]) now=x; } void da(int x,int fa,int s,int ma,int ap) { s+=aa[x]; if (ma<s) ma=s,ap=0; if (s==ma) ap++; if (s==ma&&s>=0) { if (s>dep) dep=s;if (ap>h[s]) h[s]=ap; ad(ga[s],ap); } eho(x) if (v!=fa&&(!u[v])) da(v,x,s,ma,ap); } void dbb(int x,int fa,int s,int ma,int ap) { s+=aa[x]; if (ma>s) ma=s,ap=0; if (s==ma) ap++; if (s==ma&&s<=0) { if (-s>dep) dep=-s;if (ap>h[-s]) h[-s]=ap; if (s) ad(gb[-s],ap-1); else ad(gb[0],ap); } eho(x) if (v!=fa&&(!u[v])) dbb(v,x,s,ma,ap); } inline void calc(int x){ int m; for (int i=0;i<=dep;i++) { if (ga[i]&&gb[i]) { m=h[i]; for (int j=0;j<=m;j++) A[j]=B[j]=0; for (int j=ga[i];j;j=nt[j]) A[fal[j]]++; for (int j=gb[i];j;j=nt[j]) B[fal[j]]++; mul(A,B,C,m); for (int j=m<<1;~j;j--) anw[j]+=x*C[j]; } ga[i]=gb[i]=h[i]=0; } } void sol(int x){ u[x]=1; dep=ed=0; dbb(x,0,0,N,0); eho(x) if (!u[v]) da(v,x,0,-N,0); if (gb[0]) for(int i=gb[0];i;i=nt[i]) anw[fal[i]]++; calc(1); eho(x) if (!u[v]){ dep=ed=0; da(v,x,0,-N,0); dbb(v,x,aa[x],aa[x],1); calc(-1); } eho(x) if (!u[v]) {f[0]=all=son[v];fr(v,now=0); sol(now);} } char ch[12]; signed main () { freopen("inverse.in","r",stdin); freopen("inverse.out","w",stdout); read(n); for (int i=1;i<n;i++) read(x),read(y),add(x,y),add(y,x); for (int i=1;i<=n;i++) { scanf("%s",ch); aa[i]=(ch[0]=='(')?1:-1; } f[0]=all=n; fr(1,now=0); sol(now); read(m); while (m--) read(x),writeln(anw[x]); return 0; }