没做 NOI 的现实主义者在 NOI 前最现实的做法当然是做 CNOI 系列。我 NOI 居然没做几个题。
房屋老师来拜访 hzoi 了，拜谢。
我这个实力能不能 Ag 暂时不好说。那先尽量签。
[NOI2022] 众数
本场签到题。但是赛时坑了许多人。平心而论这题赛后做比赛时做简单许多，因为能避雷。
首先看到题面第一句话发现这玩意跟摩尔投票一样。然后我们知道摩尔投票有结合律。于是我们如果不考虑前两个操作，那每个序列开个动态开点线段树维护一下摩尔投票，然后合并可以线段树合并，查询直接查每个序列摩尔投票的和，然后再统计一下这个答案在所有序列里的出现次数是否合法即可。
对于前两个操作，可以开个什么东西动态地维护序列，然后合并可以启发式合并。
然后是坑：首先这题赛时爆了一车零，因为 1e6 个 deque 会 MLE。需要 list。
然后是这题赛时一车人挂了 0-30 不等，因为查询的序列可能相同，因此统计次数要开 long long。
然后就不是很难写，写了一个小时不到写完了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <list>
using namespace std;
int n,q;
list<int>v[1000010];
struct data{
int val;
long long cnt;
data operator+(data s){
if(val==s.val)return {val,cnt+s.cnt};
else{
if(cnt>s.cnt)return {val,cnt-s.cnt};
else return {s.val,s.cnt-cnt};
}
}
};
struct node{
#define lson tree[rt].ls
#define rson tree[rt].rs
int ls,rs;
data val;
}tree[1000010<<5];
int t,rt[1000010];
void pushup(int rt){
tree[rt].val=tree[lson].val+tree[rson].val;
}
void update(int &rt,int L,int R,int pos,int val){
if(!rt)rt=++t;
if(L==R){
tree[rt].val.val=pos;
tree[rt].val.cnt+=val;
return;
}
int mid=(L+R)>>1;
if(pos<=mid)update(lson,L,mid,pos,val);
else update(rson,mid+1,R,pos,val);
pushup(rt);
}
int query(int rt,int L,int R,int pos){
if(!rt)return 0;
if(L==R)return tree[rt].val.cnt;
int mid=(L+R)>>1;
if(pos<=mid)return query(lson,L,mid,pos);
else return query(rson,mid+1,R,pos);
}
int merge(int x,int y,int l,int r){
if(!x||!y)return x|y;
if(l==r){
tree[x].val.cnt+=tree[y].val.cnt;
return x;
}
int mid=(l+r)>>1;
tree[x].ls=merge(tree[x].ls,tree[y].ls,l,mid);
tree[x].rs=merge(tree[x].rs,tree[y].rs,mid+1,r);
pushup(x);
return x;
}
int main(){
scanf("%d%d",&n,&q);int lim=n+q;
for(int i=1;i<=n;i++){
int l;scanf("%d",&l);
while(l--){
int x;scanf("%d",&x);
v[i].push_back(x);update(rt[i],1,lim,x,1);
}
}
while(q--){
int od;scanf("%d",&od);
if(od==1){
int x,y;scanf("%d%d",&x,&y);
v[x].push_back(y);
update(rt[x],1,lim,y,1);
}
else if(od==2){
int x;scanf("%d",&x);
int y=v[x].back();v[x].pop_back();
update(rt[x],1,lim,y,-1);
}
else if(od==3){
data val={0,0};
int m;scanf("%d",&m);
long long cnt=0,sum=0;
static int tmp[500010];
for(int i=1;i<=m;i++){
scanf("%d",&tmp[i]);
val=val+tree[rt[tmp[i]]].val;
sum+=v[tmp[i]].size();
}
for(int i=1;i<=m;i++)cnt+=query(rt[tmp[i]],1,lim,val.val);
if((cnt<<1)<=sum)puts("-1");
else printf("%d\n",val.val);
}
else{
int x1,x2,x3;scanf("%d%d%d",&x1,&x2,&x3);
rt[x1]=merge(rt[x1],rt[x2],1,lim);rt[x3]=rt[x1];
if(v[x1].size()<v[x2].size()){
while(!v[x1].empty())v[x2].push_front(v[x1].back()),v[x1].pop_back();
swap(v[x2],v[x3]);
}
else{
while(!v[x2].empty())v[x1].push_back(v[x2].front()),v[x2].pop_front();
swap(v[x1],v[x3]);
}
}
}
return 0;
}
[NOI2022] 挑战 NPC Ⅱ
唯二可做题。算是把到签上了，Ag 滚粗！
看到 \(k\) 比较小，于是来个暴力一点的方法。
他都说不卡哈希了我不哈希那就是不给面子。于是我们顺序搜两棵树，然后哈希值相同的直接匹配显然是最优的，哈希值不同的可以 \(O(k!)\) 暴力枚举哪对之间匹配然后暴力搜下去。
然后还需要加上一些玄学剪枝：首先如果 \(G\) 的儿子个数 / 子树大小小于 \(H\) 的儿子个数 / 子树大小显然不合法。然后如果子树大小相同直接返回哈希值相同。好像还有别的剪枝，不过不加也没什么关系，反正能过。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long ull;
int n1,n2;
ull nxt(ull x){
x^=x<<13;x^=x>>7;x^=x<<17;
return x;
}
ull hs[100010][2];
vector<int>g[100010][2];
bool cmp1(int a,int b){
return hs[a][0]<hs[b][0];
}
bool cmp2(int a,int b){
return hs[a][1]<hs[b][1];
}
int size[100010][2];
void dfs1(int x,int id){
hs[x][id]=size[x][id]=1;
for(int v:g[x][id]){
dfs1(v,id);
hs[x][id]+=nxt(hs[v][id]);
size[x][id]+=size[v][id];
}
if(id==0)sort(g[x][id].begin(),g[x][id].end(),cmp1);
else sort(g[x][id].begin(),g[x][id].end(),cmp2);
}
bool dfs(int x,int y){
if(g[x][0].size()<g[y][1].size())return false;
if(size[x][0]<size[y][1])return false;
if(size[x][0]==size[y][1])return hs[x][0]==hs[y][1];
vector<int>A,B;
int a=0,b=0;
while(a<g[x][0].size()&&b<g[y][1].size()){
if(hs[g[x][0][a]][0]==hs[g[y][1][b]][1])a++,b++;
else if(hs[g[x][0][a]][0]<hs[g[y][1][b]][1])A.push_back(g[x][0][a]),a++;
else B.push_back(g[y][1][b]),b++;
}
while(a<g[x][0].size())A.push_back(g[x][0][a]),a++;
while(b<g[y][1].size())B.push_back(g[y][1][b]),b++;
vector<int>p;
for(int i=0;i<A.size();i++)p.push_back(i);
do{
bool jud=true;
for(int i=0;i<B.size();i++){
if(size[A[p[i]]][0]<size[B[i]][1]){
jud=false;break;
}
}
if(!jud)continue;
for(int i=0;i<B.size();i++){
if(!dfs(A[p[i]],B[i])){
jud=false;break;
}
}
if(jud)return true;
}while(next_permutation(p.begin(),p.end()));
return false;
}
int main(){
int tim;scanf("%*d%d%*d",&tim);
while(tim--){
scanf("%d",&n1);
int rt1,rt2;
for(int i=1;i<=n1;i++){
int f;scanf("%d",&f);
if(f==-1)rt1=i;
else g[f][0].push_back(i);
}
scanf("%d",&n2);
for(int i=1;i<=n2;i++){
int f;scanf("%d",&f);
if(f==-1)rt2=i;
else g[f][1].push_back(i);
}
dfs1(rt1,0);dfs1(rt2,1);
if(dfs(rt1,rt2))puts("Yes");
else puts("No");
for(int i=1;i<=n1;i++)g[i][0].clear();
for(int i=1;i<=n2;i++)g[i][1].clear();
}
}
[NOI2021] 轻重边
好像 NOIP 时代考过，但是没改。现在重新写一发，还挺好写的。这年 zjk 和 hhz 老师阿克了，十分震撼。
转化一下题意：每次给一条链染色，查一条链从 \(x\) 到 \(y\) 有几条边两端颜色相同。那这个随便树剖线段树就好了。也可以 LCT，码量可能要小点。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n,m;
struct gra{
int v,next;
}edge[200010];
int t,head[100010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int num,dfn[100010],rk[100010],son[100010],size[100010],fa[100010],top[100010],dep[100010];
void dfs1(int x,int f){
size[x]=1;dep[x]=dep[f]+1;fa[x]=f;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dfs1(edge[i].v,x);
size[x]+=size[edge[i].v];
if(size[son[x]]<size[edge[i].v])son[x]=edge[i].v;
}
}
}
void dfs2(int x,int f,int tp){
dfn[x]=++num;rk[num]=x;top[x]=tp;
if(son[x])dfs2(son[x],x,tp);
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f&&edge[i].v!=son[x])dfs2(edge[i].v,x,edge[i].v);
}
}
struct data{
int l,r,sum;
friend data operator+(data s,data t){
if(s.l==0&&s.r==0)return t;
if(t.l==0&&t.r==0)return s;
data ans;
ans.l=s.l,ans.r=t.r;
ans.sum=s.sum+t.sum+(s.r==t.l);
return ans;
}
};
struct node{
#define lson rt<<1
#define rson rt<<1|1
data val;
int len,lz;
}tree[400010];
void pushup(int rt){
tree[rt].val=tree[lson].val+tree[rson].val;
}
void pushtag(int rt,int val){
tree[rt].val.l=tree[rt].val.r=val;tree[rt].val.sum=tree[rt].len-1;tree[rt].lz=val;
}
void pushdown(int rt){
if(tree[rt].lz){
pushtag(lson,tree[rt].lz);
pushtag(rson,tree[rt].lz);
tree[rt].lz=0;
}
}
void build(int rt,int l,int r){
tree[rt].len=r-l+1;
tree[rt].val={0,0,0};tree[rt].lz=0;
if(l==r){
tree[rt].val={l,l,0};return;
}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(rt);
}
void update(int rt,int L,int R,int l,int r,int val){
if(l<=L&&R<=r){
pushtag(rt,val);return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)update(lson,L,mid,l,r,val);
if(mid<r)update(rson,mid+1,R,l,r,val);
pushup(rt);
}
data query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r)return tree[rt].val;
pushdown(rt);
int mid=(L+R)>>1;data val={0,0,0};
if(l<=mid)val=val+query(lson,L,mid,l,r);
if(mid<r)val=val+query(rson,mid+1,R,l,r);
return val;
}
void change(int x,int y,int val){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,n,dfn[top[x]],dfn[x],val);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,dfn[x],dfn[y],val);
}
int query(int x,int y){
data L={0,0,0},R={0,0,0};
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]){
data ret=query(1,1,n,dfn[top[x]],dfn[x]);
L=ret+L;x=fa[top[x]];
}
else{
data ret=query(1,1,n,dfn[top[y]],dfn[y]);
R=ret+R;y=fa[top[y]];
}
}
if(dep[x]<dep[y]){
swap(L.l,L.r);
data ret=query(1,1,n,dfn[x],dfn[y]);
L=L+ret+R;
return L.sum;
}
else{
swap(R.l,R.r);
data ret=query(1,1,n,dfn[y],dfn[x]);
R=R+ret+L;
return R.sum;
}
}
int main(){
int tim;scanf("%d",&tim);
while(tim--){
scanf("%d%d",&n,&m);t=num=0;
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs1(1,0);dfs2(1,0,1);
build(1,1,n);
int cnt=n;
while(m--){
int od,u,v;scanf("%d%d%d",&od,&u,&v);
if(od==1){
cnt++;change(u,v,cnt);
}
else printf("%d\n",query(u,v));
}
for(int i=1;i<=n;i++)head[i]=son[i]=0;
}
return 0;
}
[NOI2021] 路径交点
LGV 板子。交了一发 9 和 20 挂了。拓扑排序改成 bfs 就过了。查一发是拓扑排序挂了，改成 bfs 过了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int mod=998244353;
int n,k,a[110][110],sum[110],m[110];
struct node{
int v,next;
}edge[4000010];
int t,head[20010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int cnt[20010];
bool vis[20010];
void bfs(int st){
queue<int>q;
for(int i=1;i<=sum[k];i++)cnt[i]=0,vis[i]=false;
q.push(st);cnt[st]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].next){
cnt[edge[i].v]=cnt[edge[i].v]+cnt[x];
if(cnt[edge[i].v]>=mod)cnt[edge[i].v]-=mod;
if(!vis[edge[i].v])q.push(edge[i].v),vis[edge[i].v]=true;
}
}
}
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
int gauss(int n){
int ans=1,w=1;
for(int i=1;i<=n;i++){
int mx=i;
for(int j=i+1;j<=n;j++){
if(a[j][i]>a[mx][i])mx=j;
}
if(mx!=i){
w=-w;
for(int j=1;j<=n;j++)swap(a[i][j],a[mx][j]);
}
if(!a[i][i])return 0;
int inv=qpow(a[i][i],mod-2);
for(int j=1;j<=n;j++){
if(i==j)continue;
int rate=1ll*a[j][i]*inv%mod;
for(int k=1;k<=n;k++)a[j][k]=(a[j][k]-1ll*rate*a[i][k]%mod+mod)%mod;
}
}
for(int i=1;i<=n;i++)ans=1ll*ans*a[i][i]%mod;
ans=(ans*w+mod)%mod;
return ans;
}
int main(){
int tim;scanf("%d",&tim);
while(tim--){
scanf("%d",&k);t=0;
for(int i=1;i<=k;i++)scanf("%d",&sum[i]),sum[i]+=sum[i-1];
for(int i=1;i<k;i++)scanf("%d",&m[i]);
for(int i=1;i<k;i++){
while(m[i]--){
int u,v;scanf("%d%d",&u,&v);
add(sum[i-1]+u,sum[i]+v);
}
}
for(int i=1;i<=sum[1];i++){
bfs(i);
for(int j=1;j<=sum[1];j++)a[i][j]=cnt[sum[k-1]+j];
}
printf("%d\n",gauss(sum[1]));
for(int i=1;i<=sum[k];i++)head[i]=0;
}
return 0;
}
[NOI2021] 庆典
推出了 \(k=1\)，感觉 \(k=2\) 分讨气息十分浓重。看题解发现原来不是很需要分讨，我太错。要是真考场上的话大概就 \(56\) 分滚粗了。
看到了 yhw 老师在今天早上又过了这题一遍（7.4）。
首先缩 DAG，然后根据这个道路特点手摸一下可以发现如果只保留到每个点的最长路的话是棵树。于是问题放到树上。\(k=0\) 就是链和，\(k=1\) 简单分讨一下跳不跳。\(k=2\) 比较麻烦。
考虑不去分讨。对 \(2k\) 个点加上 \(s,t\) 两个点建虚树，边有边权。于是问题又回到有向图上从 \(s\) 到 \(t\) 的权值和。这个点数是 \(O(k)\) 的，可以直接爆扫一遍可达性求并。
代码先咕。今天不太想每个题写四五 k 代码。
[NOI2021] 密码箱
比较签的题，但是有个式子忘了贺了一发）
大概是我唯一能做出来的 Day2 T2。
首先这题的 key observation 是 \(f\) 是连分数，然后连分数的每个渐进分数的分子分母都是互质的而且可以递推。具体递推式：设第 \(k\) 项为 \(p_k,q_k\)，则有
\[p_k=a_kp_{k-1}+p_{k-2}\qquad q_k=a_kq_{k-1}+q_{k-2}
\]
\[p_{-1}=1\quad p_0=a_0\qquad q_{-1}=0\quad q_0=1
\]
看到递推想到矩阵维护，每项的矩阵就是 \(\left(\begin{matrix}a_k & 1\\1 & 0\end{matrix}\right)\)。看两种修改：
W：显然 \(\left(\begin{matrix}1 & 0\\1 & 1\end{matrix}\right)\)。E：不是很显然。第一个操作是左乘个W的矩阵，第二个是\[\left(\begin{matrix}1 & 0\\1 & 1\end{matrix}\right)^{-1}\left(\begin{matrix}1 & 1\\1 & 0\end{matrix}\right)\left(\begin{matrix}1 & 1\\1 & 0\end{matrix}\right)=\left(\begin{matrix}2 & 1\\-1 & 0\end{matrix}\right) \]然后可以发现在 \(a_k=1\) 时两种操作是等价的，于是可以直接看做 \(\left(\begin{matrix}2 & 1\\-1 & 0\end{matrix}\right)\)。
写了一个小时线段树突然发现 tmd 要写平衡树，写 nm。
代码先咕。今天不太想每个题写四五 k 代码。
[NOI2020] 美食家
好像签了这个然后剩下五个骗 \(100\) 分就能 Ag。不过这一年的 Day2 十分困难。
首先这玩意如果 \(w=1\) 看起来就是个矩阵乘法的形式，于是广义矩阵乘。然后 \(w\le 5\) 考虑拆点，把每个点拆成 \(5\) 个然后连边。然后美食节单独处理，复杂度是 \(O((5n)^3k\log T)\) 的，看上去很过不去。
然而发现我们最后只需要 \((1,1)\) 位置的值，于是只需要维护一个行向量的乘法即可，加上预处理转移矩阵的 \(2^n\) 次幂，复杂度 \(O((5n)^3\log T+(5n)^2k\log T)\)，常数十分小可以过去。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int mod=998244353;
int n,m,T,k,c[60],id[60][5],cnt;
struct Mat{
long long a[310][310];
Mat(){memset(a,-0x3f,sizeof(a));}
Mat operator*(const Mat&s)const{
Mat ret;
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++){
for(int k=1;k<=cnt;k++){
ret.a[i][j]=max(ret.a[i][j],a[i][k]+s.a[k][j]);
}
}
}
return ret;
}
}P[31];
struct Vec{
long long a[310];
Vec(){memset(a,-0x3f,sizeof(a));}
Vec operator*(const Mat&s)const{
Vec ret;
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++){
ret.a[j]=max(ret.a[j],a[i]+s.a[i][j]);
}
}
return ret;
}
}ans;
struct Ques{
int t,x,y;
bool operator<(const Ques&s)const{
return t<s.t;
}
}p[210];
int main(){
scanf("%d%d%d%d",&n,&m,&T,&k);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);ans.a[1]=c[1];
for(int i=1;i<=n;i++){
for(int j=0;j<5;j++)id[i][j]=++cnt;
for(int j=1;j<5;j++)P[0].a[id[i][j-1]][id[i][j]]=0;
}
for(int i=1;i<=m;i++){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
P[0].a[id[u][w-1]][id[v][0]]=c[v];
}
for(int i=1;i<=30;i++)P[i]=P[i-1]*P[i-1];
for(int i=1;i<=k;i++)scanf("%d%d%d",&p[i].t,&p[i].x,&p[i].y);p[k+1]={T,0,0};
sort(p+1,p+k+1);
for(int i=1;i<=k+1;i++){
int tmp=p[i].t-p[i-1].t;
for(int j=30;j>=0;j--){
if((tmp>>j)&1)ans=ans*P[j];
}
ans.a[id[p[i].x][0]]+=p[i].y;
}
ans.a[1]=max(ans.a[1],-1ll);
printf("%lld\n",ans.a[1]);
return 0;
}
[NOI2020] 命运
会状态定义就是水题，但是我菜的连状态定义都出不来。
观察性质发现以某个点为下端的只有最深的上端有用，于是设 \(dp_{x,i}\) 为到 \(x\) 最深的没满足的上端点为 \(i\) 的方案数，如果都满足就是 \(0\)。那么转移考虑合并子树：
- 这条边是 \(0\)：贡献显然 \(dp_{x,i}\leftarrow\sum_{\max_{a,b}=i}dp_{x,a}dp_{v,b}\)。
- 是 \(1\)：同样 \(dp_{x,i}\leftarrow dp_{x,i}\times\sum_{j=0}^{dep_x}dp_{v,j}\)。
线段树合并即可。但是 pushup 不取模居然能过所有大样例。这告诉我们场上一定要拍。上次调了一下午也是 pushup 没取模。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int mod=998244353;
int n,m;
struct gra{
int v,next;
}edge[1000010];
int tot,head[500010];
void add(int u,int v){
edge[++tot].v=v;edge[tot].next=head[u];head[u]=tot;
}
int mx[500010],dep[500010];
void dfs1(int x,int f){
dep[x]=dep[f]+1;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f)dfs1(edge[i].v,x);
}
}
struct node{
#define lson tree[rt].ls
#define rson tree[rt].rs
int ls,rs,sum,lz;
}tree[500010<<5];
int t,rt[500010];
void pushup(int rt){
tree[rt].sum=(tree[lson].sum+tree[rson].sum)%mod;
}
void pushtag(int rt,int val){
tree[rt].sum=1ll*tree[rt].sum*val%mod;
tree[rt].lz=1ll*tree[rt].lz*val%mod;
}
void pushdown(int rt){
if(tree[rt].lz!=1){
if(lson)pushtag(lson,tree[rt].lz);
if(rson)pushtag(rson,tree[rt].lz);
tree[rt].lz=1;
}
}
void update(int &rt,int L,int R,int pos,int val){
if(!rt)rt=++t,tree[rt].lz=1;
if(L==R){
tree[rt].sum=val;return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(pos<=mid)update(lson,L,mid,pos,val);
else update(rson,mid+1,R,pos,val);
pushup(rt);
}
int query(int rt,int L,int R,int l,int r){
if(!rt)return 0;
if(l<=L&&R<=r)return tree[rt].sum;
pushdown(rt);
int mid=(L+R)>>1,val=0;
if(l<=mid)val=(val+query(lson,L,mid,l,r))%mod;
if(mid<r)val=(val+query(rson,mid+1,R,l,r))%mod;
return val;
}
int merge(int x,int y,int l,int r,int sumx,int sumy,int val){
if(!x&&!y)return 0;
if(!x){
pushtag(y,sumx);
return y;
}
if(!y){
pushtag(x,(val+sumy)%mod);
return x;
}
if(l==r){
tree[x].sum=(1ll*(val+sumy)%mod*tree[x].sum%mod+1ll*tree[y].sum*sumx%mod+1ll*tree[x].sum*tree[y].sum%mod)%mod;
return x;
}
pushdown(x);pushdown(y);
int mid=(l+r)>>1;
tree[x].rs=merge(tree[x].rs,tree[y].rs,mid+1,r,(sumx+tree[tree[x].ls].sum)%mod,(sumy+tree[tree[y].ls].sum)%mod,val);
tree[x].ls=merge(tree[x].ls,tree[y].ls,l,mid,sumx,sumy,val);
pushup(x);
return x;
}
void dfs(int x,int f){
update(rt[x],0,n,mx[x],1);
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dfs(edge[i].v,x);
rt[x]=merge(rt[x],rt[edge[i].v],0,n,0,0,query(rt[edge[i].v],0,n,0,dep[x]));
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs1(1,0);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
mx[v]=max(mx[v],dep[u]);
}
dfs(1,0);
printf("%d\n",query(rt[1],0,n,0,0));
return 0;
}