0%

省选 2019 补题记录

如题。

目前进度:

T1代码 T1题解 T2代码 T2题解 T3代码 T3题解
ZJOI2019 Day1 $\sqrt{}$ $\sqrt{}$ $\sqrt{}$ $\sqrt{}$ $\sqrt{}$ $\sqrt{}$
ZJOI2019 Day2 $\sqrt{}$ $\sqrt{}$ $\sqrt{}$ $\sqrt{}$

ZJOI2019 Day1

T1

题目链接

对麻将的热爱消失殆尽了(悲)

考虑怎么判断一副牌是胡的。我们有一个 DP 做法:设 $f_{i,j_1,j_0,k}$ 是考虑面值为 $1…i$ 的所有牌,预留的 $(i-1,i,i+1)$ 顺子数目为 $j_1$,预留的 $(i,i+1,i+2)$ 顺子数目为 $j_0$,$k$ 是有没有预留过对子,的最大面子数。还要再加一维表示总共有多少对子来判断七对子。显然 $j_1,j_0<3$,否则可以拆成刻子。

判断能否胡牌很简单,$f_i,\star,\star,1$ 中有一个大于等于 $4$ 或者有七个对子即可。

显然这个 DP 和 $i$ 完全没有关系,和 $k$ 也关系不大,它可以看成一个 $2\times 3\times 3$ 的矩阵,接受一个数后转移成另一个矩阵,可以看成一个自动机。走到胡节点即胡牌。

那么我们就可以考虑在这个自动机上 DP 了,设 $g_{i,j,p}$ 是考虑了面值为 $1…i$ 的牌,摸了其中 $j$ 张,走到了自动机节点 $p$ 的概率。我们都知道胡牌期望就是 $\sum_{i=0}^\infty P(\texttt{摸了 i 张牌还不胡})$,大力 DP 即可。

代码如下,写得简直让人想吐:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
using namespace std;

struct Mat{
int a[3][3];
Mat (bool flg=0){memset(a,-1,sizeof(a));if(flg) a[0][0]=0;}
Mat calc(Mat &c,const int x){
for(int j2=0;j2<3;j2++)
for(int j1=0;j1<3;j1++)if(a[j2][j1]!=-1)
for(int j0=0;j0<3&&j2+j1+j0<=x;j0++)
c.a[j1][j0]=max(c.a[j1][j0],min(a[j2][j1]+j2+(x-j2-j1-j0)/3,4));
return c;
}
bool operator <(const Mat b)const{
for(int j1=0;j1<3;j1++)
for(int j0=0;j0<3;j0++)
if(a[j1][j0]!=b.a[j1][j0]) return a[j1][j0]<b.a[j1][j0];
return 0;
}
bool operator !=(const Mat b)const{
for(int j1=0;j1<3;j1++)
for(int j0=0;j0<3;j0++)
if(a[j1][j0]!=b.a[j1][j0]) return 1;
return 0;
}
bool const ishu()const{
for(int j1=0;j1<3;j1++)
for(int j0=0;j0<3;j0++)
if(a[j1][j0]>=4) return 1;
return 0;
}
};
struct AM{ //自动机怪!
Mat F[2];int dbcnt;
AM (bool flg=0){if(!flg) F[0]=F[1]=Mat(),dbcnt=-0x3f3f3f3f;else F[0]=Mat(1),F[1]=Mat(),dbcnt=0;}
void HU(){dbcnt=998244353;F[0]=F[1]=Mat();}
bool ishu(){
if(dbcnt==998244353) return 1;
if(dbcnt>=7){HU();return 1;}
if(F[1].ishu()){HU();return 1;}
return 0;
}
bool operator <(const AM b)const{
if(dbcnt!=b.dbcnt) return dbcnt<b.dbcnt;
if(F[0]!=b.F[0]) return F[0]<b.F[0];
if(F[1]!=b.F[1]) return F[1]<b.F[1];
return 0;
}
AM calc(int x){
if(ishu()) return (*this);
AM c;
if(x>=2) F[0].calc(c.F[1],x-2);
F[0].calc(c.F[0],x);
F[1].calc(c.F[1],x);
c.dbcnt=dbcnt+(x>=2);
c.ishu();
return c;
}
};
map<AM,int>id;int tot;int G[2500][5];queue<AM> que;
int T;
void BFS(){
AM st(1);
que.push(st);id[st]=++tot;
while(!que.empty()){
AM u=que.front();que.pop();
if(u.ishu()){T=id[u];continue;}
for(int x=0;x<=4;x++){
AM v=u.calc(x);
if(id.count(v)) G[id[u]][x]=id[v];
else G[id[u]][x]=id[v]=++tot,que.push(v);
}
}
}

const int p=998244353;
int fac[2500],ifac[2500],inv[2500];
void init(){
inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
for(int i=2;i<2500;i++)
inv[i]=1LL*(p-p/i)*inv[p%i]%p,
fac[i]=1LL*fac[i-1]*i%p,
ifac[i]=1LL*ifac[i-1]*inv[i]%p;
}

int N,A[105];

int F[105][405][2500];
int val[5];

int main(){
init();BFS();
scanf("%d",&N);
for(int i=1;i<=13;i++){int x,y;scanf("%d%d",&x,&y);A[x]++;}
F[0][0][1]=1;
for(int d=1;d<=N;d++){
for(int k=0;k<=4-A[d];k++) val[k]=1LL*fac[4-A[d]]*ifac[k]%p*ifac[4-A[d]-k]%p;
for(int i=0;i<=4*N-13;i++)
for(int j=1;j<=tot;j++)
for(int k=A[d];k<=4;k++)
(F[d][i+k-A[d]][G[j][k]]+=1LL*F[d-1][i][j]*val[k-A[d]]%p)%=p;
}
int ans=0;
for(int i=0;i<=4*N-13;i++)
for(int j=1;j<=tot;j++) if(j!=T)
(ans+=1LL*F[N][i][j]*fac[i]%p*fac[4*N-13-i]%p)%=p;
printf("%d\n",1LL*ans*ifac[4*N-13]%p);
}

T2

题目链接

考虑维护 $f_u$ 为 $u$ 有 tag 的概率,$g_u$ 为 $u$ 及其祖先中至少有一个 tag 的概率。

分如上五类点大力讨论:

  • 白色
  • 红色
  • 灰色
  • 黄色
  • 橙色

然后线段树维护即可。

因不明原因要开 8 倍空间?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;

const int p=998244353,inv2=(p+1)/2;
void inline check(int &x){x-=p,x+=x>>31&p;}
int N,M;

int pow2[200005];
int f[800005],g[800005],sf[800005],lzy[800005];
void add(int x,int k){
check(g[x]=1LL*g[x]*pow2[k]%p+1-pow2[k]+p);
lzy[x]+=k;
}
void pushup(int x){check(sf[x]=f[x]+sf[x<<1]);check(sf[x]+=sf[x<<1|1]);}
void pushdown(int x){
if(!lzy[x]) return;
add(x<<1,lzy[x]);add(x<<1|1,lzy[x]);lzy[x]=0;
}
void Update(int x,int l,int r,int L,int R){
if(r<L||l>R){//orange
check(f[x]+=g[x]);f[x]=1LL*f[x]*inv2%p;
pushup(x);return;
}
if(L<=l&&r<=R){//red
f[x]=1LL*(f[x]+1)*inv2%p;g[x]=1LL*(g[x]+1)*inv2%p;
if(l!=r) pushdown(x),add(x<<1,1),add(x<<1|1,1);//gray
pushup(x);return;
}
f[x]=1LL*f[x]*inv2%p,g[x]=1LL*g[x]*inv2%p;//white
int mid=(l+r)>>1;pushdown(x);
Update(x<<1,l,mid,L,R);Update(x<<1|1,mid+1,r,L,R);
pushup(x);
}
void Query(int x,int l,int r){
printf("check [%d,%d] : %d %d\n",l,r,f[x],g[x]);
if(l!=r){
int mid=(l+r)>>1;pushdown(x);
Query(x<<1,l,mid);Query(x<<1|1,mid+1,r);
}
}

int main(){
pow2[0]=1;for(int i=1;i<=200000;i++) pow2[i]=1LL*pow2[i-1]*inv2%p;
scanf("%d%d",&N,&M);
int ans=1;
for(int i=1;i<=M;i++){
int opt;scanf("%d",&opt);
if(opt==1){
int L,R;scanf("%d%d",&L,&R);
Update(1,1,N,L,R);
check(ans+=ans);
}
else printf("%d\n",1LL*sf[1]*ans%p);
}
}

T3

题目链接

考虑差分:求稳定度 $\le k$ 的集合数量。

记某个点 $u$ 的权值为 $v(u)$。考虑 $v=W$ 的节点显然形成了一条由根到叶子的链。每个其他叶子也会向上延伸出一条链,直到撞到主链或者其他链。

只要主链上有一个点改变 $W$ 就传不到根了;于是可以断开主链上的所有边分别考虑。

考虑对叶子节点的策略是什么?如果当前根的深度为奇数,那么必然取 $W+1$:既能最终胜过 $W$,又更不容易因为太大在偶数深度被淘汰。偶数同理。于是对于确定的 $k$,每个叶子的策略是确定的,和 rand() 出的集合无关。

考虑 DP:$\text{f}_u$ 表示:对于深度为奇数的 $u$,有多少种叶子集合能让 $v(u)>W$。对于偶数反之。

“能”字在这里可能引发误解:对于每个集合,策略是完全确定的,不会有哪个集合既“能”使 $v\le W$ 又“能”使 $v>W$。

记 $u$ 子树中的叶子数为 $\text{siz}_u$。

明确完了上面几点,接下来写 DP 方程。

对于叶子节点,

最终计算答案时只需要把每个主链上的节点乘起来。

当 $k$ 变动时每个叶子的 $\text{f}$ 只会变动一次,提示我们动态 DP。于是就做完了。注意由于 $\text{f}_v$ 可能为 0,而除以 0 非常麻烦,所以考虑从大到小枚举 $k$。

思路非常线性,冷静分析一下应该不算太难?那么问题来了该如何学会冷静分析呢

代码非常恶心……看来调试能力也是不可或缺的一部分啊……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
using namespace std;

const int maxN=400005;

int N,L,R;
vector<int> G[maxN];
void add_E(int u,int v){G[u].push_back(v);}

int tf[maxN],W;
int lsiz[maxN],dep[maxN];
vector<int> Ls;
bool isleaf(int x){return G[x].size()==1&&x!=1;}
void init1(int u,int f){
dep[u]=dep[f]+1;
if(isleaf(u)){Ls.push_back(u);tf[u]=u;return;}
if(dep[u]&1) tf[u]=-0x3f3f3f3f;else tf[u]=0x3f3f3f3f;
for(auto v : G[u]) if(v!=f){
init1(v,u);
if(dep[u]&1) tf[u]=max(tf[u],tf[v]);else tf[u]=min(tf[u],tf[v]);
}
}

int fa[maxN],siz[maxN],son[maxN];
int top[maxN],tal[maxN],seg[maxN],rev[maxN],idx;
void dfs1(int u,int f){
fa[u]=f;siz[u]=1;
for(auto v : G[u]) if(v!=f&&tf[v]!=W){
dfs1(v,u);siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int f){
top[u]=(u==son[f]?top[f]:u);
rev[seg[u]=++idx]=u;
if(son[u]) dfs2(son[u],u),tal[u]=tal[son[u]];else tal[u]=u;
for(auto v : G[u]) if(v!=f&&v!=son[u]&&tf[v]!=W) dfs2(v,u);
}

const int p=998244353;
int qpow(int a,int k){
int ans=1;
while(k){
if(k&1) ans=1LL*ans*a%p;
a=1LL*a*a%p;
k>>=1;
}
return ans;
}
int pow2[maxN];
struct Mat{
int k,b;
Mat (int k0=1,int b0=0){k=k0,b=b0;}
Mat operator *(const Mat y)const{
return Mat(1LL*k*y.k%p,(1LL*k*y.b%p+b)%p);
}
}T[maxN<<2],initT[maxN];
int F[maxN],rt[maxN];
int calc(int u,int K){
if(dep[rt[u]]&1)
if(dep[u]&1) return (u>W)+(u+K>W);
else return (u<=W)+(u+K<=W);
else if(dep[u]&1) return (u>=W)+(u-K>=W);
else return (u<W)+(u-K<W);
}
void init2(int u,int f,int rt0){
rt[u]=rt0;
if(isleaf(u)){
lsiz[u]=1;
initT[u].b=F[u]=calc(u,N-1);
return;
}
initT[u].k=p-1;F[u]=1;
for(auto v : G[u]) if(v!=f&&tf[v]!=W){
init2(v,u,rt0);lsiz[u]+=lsiz[v];
if(v!=son[u]) initT[u].k=1LL*initT[u].k*F[v]%p;
F[u]=1LL*F[u]*F[v]%p;
}
F[u]=(pow2[lsiz[u]]-F[u]+p)%p;initT[u].b=pow2[lsiz[u]];
}
int ans=1; //当前稳定的集合数
int ANS[maxN];

void Build(int x,int l,int r){
if(l==r){T[x]=initT[rev[l]];return;}
int mid=(l+r)>>1;
Build(x<<1,l,mid);Build(x<<1|1,mid+1,r);
T[x]=T[x<<1]*T[x<<1|1];
}
void Update(int x,int l,int r,int pos){
if(l==r){T[x]=initT[rev[l]];return;}
int mid=(l+r)>>1;
if(pos<=mid) Update(x<<1,l,mid,pos);
if(pos>mid) Update(x<<1|1,mid+1,r,pos);
T[x]=T[x<<1]*T[x<<1|1];
}
Mat Query(int x,int l,int r,int L,int R){
if(L<=l&&r<=R) return T[x];
int mid=(l+r)>>1;
if(L>mid) return Query(x<<1|1,mid+1,r,L,R);
if(R<=mid) return Query(x<<1,l,mid,L,R);
return Query(x<<1,l,mid,L,R)*Query(x<<1|1,mid+1,r,L,R);
}
vector<int> upds[maxN];

int main(){
pow2[0]=1;for(int i=1;i<maxN;i++) pow2[i]=(pow2[i-1]<<1)%p;
scanf("%d%d%d",&N,&L,&R);
for(int i=1;i<N;i++){
int u,v;scanf("%d%d",&u,&v);
add_E(u,v);add_E(v,u);
}
init1(1,0);W=tf[1];
for(int i=1;i<=N;i++) if(tf[i]==W) dfs1(i,0);
for(int i=1;i<=N;i++) if(tf[i]==W) dfs2(i,0);
for(int i=1;i<=N;i++) if(tf[i]==W) init2(i,0,i);
for(int i=1;i<=N;i++) if(tf[i]==W) ans=1LL*(pow2[lsiz[i]]-F[i]+p)%p*ans%p;
Build(1,1,N);
for(auto u : Ls)
if(dep[rt[u]]&1)
if(dep[u]&1) {if(W-u>=0) upds[W-u].push_back(u);}
else {if(W-u>=0) upds[W-u].push_back(u);}
else if(dep[u]&1) {if(u-W>=0) upds[u-W].push_back(u);}
else {if(u-W>=0) upds[u-W].push_back(u);}
ANS[N]=ans-1;
for(int K=N-2;K>=0;K--){
int tans=ans;
for(auto u : upds[K]){
if(u!=rt[u]) initT[u].b=calc(u,K);else initT[u].b=0;
int bef,aft;
while(1){
bef=Query(1,1,N,seg[top[u]],seg[tal[u]]).b;
Update(1,1,N,seg[u]);
aft=Query(1,1,N,seg[top[u]],seg[tal[u]]).b;
if(fa[top[u]]){
u=fa[top[u]];
initT[u].k=1LL*initT[u].k*qpow(bef,p-2)%p*aft%p;
}
else{
u=top[u];
ans=1LL*(pow2[lsiz[u]]-aft+p)%p*ans%p*qpow((pow2[lsiz[u]]-bef+p)%p,p-2)%p;
break;
}
}
}
ANS[K+1]=(ans-tans+p)%p;
}
for(int i=L;i<=R;i++) printf("%d ",ANS[i]);
}

ZJOI2019 Day2

觉得 Day2 比 Day1 简单是怎么回事?

T1

题目链接

首先考虑“第一次”怎么处理。设 $F$ 是 $i$ 步操作恰好第一次达成目标的 OGF,$G$ 是 $i$ 步操作走回原状态的 OGF,$H$ 是 $i$ 步操作达成目标的 OGF。显然有

而 $g$ 就是把终状态改掉的 $H$。

令 $p_i\leftarrow p_i/\sum p$,容易写出 $\hat H$($\hat{\ }$ 表示EGF)为

对 $e^{ix/\sum p}$ 大力 DP。于是我们可以得到

众所周知概率生成函数求导后在 1 处的值就是期望:

这里有一个问题。$x=1$ 时这是一个 $\dfrac{\infty}{\infty}$ 形的极限,而洛必达只会越洛越复杂。这里考虑给 $H,G$ 都乘上 $1-x$ 就没这个问题了。

具体式子忘了。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;

const int p=998244353,inv2=499122177;
const int maxN=105,maxP=50005;

int qpow(int a,int k){
int ans=1;
while(k){
if(k&1) ans=1LL*ans*a%p;
a=1LL*a*a%p;
k>>=1;
}
return ans;
}

int N,SP;
int _A[maxP<<1],_B[maxP<<1],*A=_A+maxP,*B=_B+maxP;
int _tA[maxP<<1],_tB[maxP<<1],*tA=_tA+maxP,*tB=_tB+maxP;
int s[maxN],P[maxN];

int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++) scanf("%d",&s[i]);
A[0]=B[0]=1;
for(int i=1;i<=N;i++){
scanf("%d",&P[i]);
for(int j=-SP-P[i];j<=SP+P[i];j++) tA[j]=tB[j]=0;
for(int j=-SP;j<=SP;j++){
tA[j+P[i]]=(tA[j+P[i]]+1LL*inv2*A[j]%p)%p;
if(s[i]&1)
tA[j-P[i]]=(tA[j-P[i]]-1LL*inv2*A[j]%p+p)%p;
else
tA[j-P[i]]=(tA[j-P[i]]+1LL*inv2*A[j]%p)%p;
tB[j+P[i]]=(tB[j+P[i]]+1LL*inv2*B[j]%p)%p;
tB[j-P[i]]=(tB[j-P[i]]+1LL*inv2*B[j]%p)%p;
}
swap(tA,A);swap(tB,B);
SP+=P[i];
}
int invSP=qpow(SP,p-2),ans=0;
for(int j=-SP;j<=SP;j++)
ans=(ans+1LL*(1LL*A[j]*B[SP]%p-1LL*A[SP]*B[j]%p+p)%p*qpow((1LL*(j+p)%p*invSP%p-1+p)%p,p-2)%p)%p;
ans=1LL*ans*qpow(B[SP],p-3)%p;
printf("%d\n",ans);
}

T2

题目链接

考虑一个点 $u$ 能到达的 $v$。显然是一堆通过了 $u$ 的链之并。事实上再冷静分析一下你会发现这是一个虚树的大小。链上打 tag 之类的东西必然要两个 log 以上,考虑树上差分。合并的时候线段树合并即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxN=100005;
int N,M;

int lnk[maxN];
int pre[maxN<<1],tgt[maxN<<1],cnt;
void add_E(int u,int v){
pre[++cnt]=lnk[u],tgt[cnt]=v,lnk[u]=cnt;
}
int Tin[maxN],idx0,T[maxN<<1];
int dfn[maxN],idx1;
int dep[maxN],fa[maxN];
void dfs(int x,int f){
dfn[x]=++idx1;
Tin[x]=++idx0;T[idx0]=x;
for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=f)
dep[tgt[e]]=dep[x]+1,fa[tgt[e]]=x,dfs(tgt[e],x),T[++idx0]=x;
}
int lg2[maxN<<1],ST[maxN<<1][20];
int mymin(int u,int v){
return dep[u]<dep[v]?u:v;
}
void Get_ST(){
lg2[0]=-1;
for(int i=1;i<=N<<1;i++) lg2[i]=lg2[i>>1]+1;
for(int i=idx0;i;i--){
ST[i][0]=T[i];
for(int k=1;i+(1<<k)-1<=idx0;k++)
ST[i][k]=mymin(ST[i][k-1],ST[i+(1<<(k-1))][k-1]);
}
}
int LCA(int u,int v){
if(!u||!v) return 0;
u=Tin[u],v=Tin[v];
if(u>v) swap(u,v);
int k=lg2[v-u+1];
return mymin(ST[u][k],ST[v-(1<<k)+1][k]);
}

int RT[maxN];
int Ln[maxN*80],Rn[maxN*80],C[maxN*80],lc[maxN*80],rc[maxN*80],tot;
ll F[maxN*80];
void pushup(int x){
C[x]=C[lc[x]]+C[rc[x]];
Ln[x]=Ln[lc[x]]?Ln[lc[x]]:Ln[rc[x]];
Rn[x]=Rn[rc[x]]?Rn[rc[x]]:Rn[lc[x]];
F[x]=F[lc[x]]+F[rc[x]]-dep[LCA(Rn[lc[x]],Ln[rc[x]])];
}
void Update(int &x,int l,int r,int pos,bool flg){
if(!x) x=++tot;
if(l==r){
if(flg){C[x]--;if(!C[x]) F[x]=Ln[x]=Rn[x]=0;}
else{if(!C[x]) F[x]=dep[pos],Ln[x]=Rn[x]=pos;C[x]++;}
return;
}
int mid=(l+r)>>1;
if(dfn[pos]<=mid) Update(lc[x],l,mid,pos,flg);
else Update(rc[x],mid+1,r,pos,flg);
pushup(x);
}
ll Query(int x){
return F[x]-dep[LCA(Ln[x],Rn[x])];
}
void Merge(int &x,int y,int l,int r){
if(!x||!y){x=x+y;return;}
if(l==r){
Ln[x]|=Ln[y];Rn[x]|=Rn[y];F[x]|=F[y];C[x]+=C[y];
return;
}
int mid=(l+r)>>1;
Merge(lc[x],lc[y],l,mid);
Merge(rc[x],rc[y],mid+1,r);
pushup(x);
}
void Debug(int x,int l,int r){
if(!x){return;}
if(l==r){return;}
int mid=(l+r)>>1;
Debug(lc[x],l,mid);Debug(rc[x],mid+1,r);
}

vector<int> Inc[maxN],Dec[maxN];
ll ans;
void Solve(int u){
for(int j=0;j<Inc[u].size();j++)
Update(RT[u],1,N,Inc[u][j],0);
for(int e=lnk[u];e;e=pre[e]) if(tgt[e]!=fa[u]) Solve(tgt[e]);
for(int j=0;j<Dec[u].size();j++)
Update(RT[u],1,N,Dec[u][j],1);
ans+=Query(RT[u]);
Merge(RT[fa[u]],RT[u],1,N);
}

int main(){
scanf("%d%d",&N,&M);
for(int i=1;i<N;i++){
int u,v;scanf("%d%d",&u,&v);
add_E(u,v);add_E(v,u);
}
dfs(1,0);Get_ST();
for(int i=1;i<=M;i++){
int u,v,w;scanf("%d%d",&u,&v);w=LCA(u,v);
Dec[w].push_back(u);Dec[w].push_back(v);
Dec[fa[w]].push_back(u);Dec[fa[w]].push_back(v);
Inc[u].push_back(u);Inc[u].push_back(v);
Inc[v].push_back(u);Inc[v].push_back(v);
}
Solve(1);
printf("%d\n",ans>>1);
return 0;
}

T3

不会半平面交啊qaq