My Blogs
首先连通块个数可以用经典的点边转化，用点的个数减去边的条数。
观察之后可以发现定合法的充要条件是黑色的点构成一个连通块，同样使用点边转化。
现在可以看成有两个序列（时间轴），$V$ 和 $S$，操作是区间 $v$ 的修改，区间 $s$ 的修改，和查询全局 $v=1$ 的 $s$ 的和。
对于一个点，设 $p_i$ 为其出现时间，则其在 $[1,p_i-1]$ 上对 $v$ 有 $1$ 的贡献，在 $[p_i,n]$ 上对 $s$ 有 $1$ 的贡献。
对于一条边，设 $p_1$ 为两端点出现较早的时间，$p_2$ 为较晚点的出现时间，则其在 $[1,p_1-1]$ 上对 $v$ 有 $-1$ 的贡献，在 $[p_2,n]$ 上对 $s$ 有 $-1$ 的贡献。
容易发现操作一定保证 $v\geq 1$，所以线段树维护区间 $v$ 是最小值的 $s$ 的和，修改就直接把原来边的贡献删掉，再加入新的边。经典答案和树形态无关，复杂度是 $\mathcal O((n+q)\log n)$。
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
int n,m,a[500010];
vector<pii> ve;
namespace Segment
{
#define ls(x) (t[x].l+t[x].r)
#define rs(x) (ls(x)^1)
struct{int l,r,v,s,sz,tg1,tg2;}t[1000010];
inline void update(int x)
{
t[x].v=min(t[ls(x)].v,t[rs(x)].v),t[x].s=t[x].sz=0;
if(t[x].v==t[ls(x)].v)t[x].s+=t[ls(x)].s,t[x].sz+=t[ls(x)].sz;
if(t[x].v==t[rs(x)].v)t[x].s+=t[rs(x)].s,t[x].sz+=t[rs(x)].sz;
}
inline void down1(int p,int x){t[p].tg1+=x,t[p].v+=x;}
inline void down2(int p,int x){t[p].tg2+=x,t[p].s+=t[p].sz*x;}
inline void spread(int p)
{
down1(ls(p),t[p].tg1),down1(rs(p),t[p].tg1);
down2(ls(p),t[p].tg2),down2(rs(p),t[p].tg2);
t[p].tg1=t[p].tg2=0;
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r)return t[p].sz=1,t[p].v=l==n,void();
int mid=l+((r-l)>>1);
build(ls(p),l,mid),build(rs(p),mid+1,r),update(p);
}
void modify1(int p,int l,int r,int x)
{
if(l<=t[p].l&&r>=t[p].r)return down1(p,x);
spread(p);
if(l<=t[ls(p)].r)modify1(ls(p),l,r,x);
if(r>t[ls(p)].r)modify1(rs(p),l,r,x);
update(p);
}
void modify2(int p,int l,int r,int x)
{
if(l<=t[p].l&&r>=t[p].r)return down2(p,x);
spread(p);
if(l<=t[ls(p)].r)modify2(ls(p),l,r,x);
if(r>t[ls(p)].r)modify2(rs(p),l,r,x);
update(p);
}
void print(int p)
{
write(t[p].l,' ',t[p].r,' ',t[p].v,' ',t[p].s,'\n');
if(t[p].l==t[p].r)return;
spread(p),print(ls(p)),print(rs(p));
}
}
using namespace Segment;
inline void add(pii p,int v)
{
if(a[p.fi]>a[p.se])swap(p.fi,p.se);
if(a[p.fi]>1)modify1(1,1,a[p.fi]-1,-v);
modify2(1,a[p.se],n,-v);
}
inline void add(int p,int v)
{
if(a[p]>1)modify1(1,1,a[p]-1,v);
modify2(1,a[p],n,v);
}
inline void mian()
{
read(n,m),a[1]=n,build(1,1,n);int x,y;
for(int i=1;i<n;++i)read(x,y),ve.eb(mp(x,y));
for(int i=1;i<n;++i)read(x),a[x]=i;
for(int i=1;i<=n;++i)add(i,1);
for(auto p:ve)add(p,1);
if(t[1].v==1)write(t[1].s-1,'\n');
else puts("0");
while(m--)
{
read(x,y),add(mp(x,y),-1),read(x,y),add(mp(x,y),1);
if(t[1].v==1)write(t[1].s-1,'\n');
else puts("0");
}
}