义乌中学暑假集训 2021.07.10 D

(Updated: )
oi

Description

给定一棵 $n$ 个节点的树，有 $m$ 个询问，每次给定 $l,r$，查询若只保留点编号在 $[l,r]$ 的点，边编号在 $[l,r]$ 的边，有多少个连通块。

此时点 $a$ 与点 $b$ 连通当且仅当 $l\leq a,b\leq r$，且 $a,b$ 在树上的简单路径中所有的点与边的编号都在 $[l,r]$ 之间。

$1\leq n,m\leq 10^6$。

Solution

考虑连通块个数=点数-边数。

而点数 $=r-l+1$​ 是确定的，那么只需要考虑如何维护边数即可。

那么如何判断是否是有用的边？

其实就等价于对于边 $i$，满足 $l\leq i\leq r$，并且 $i$ 连接的两个点 $x,y$，满足 $l\leq x,y\leq r$。

也就是说，对于边 $i$，需要满足 $l\leq \min(i,x,y)\leq \max(i,x,y)\leq r$​。

然后这题就成了二维数点问题。

可以先把询问离线。

按照 $r$ 从小到大，依次加入点与边。

然后用树状数组维护即可。

Code

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
#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
#define LL long long
using namespace std;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(RI x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x%10+'0');}
Cn int N=1e6+10;
int n,m,Ans[N];
struct Edge{int x,y;}e[N];
struct Que{int x,y,id;}q[N];
I bool cmp(Cn Edge& x,Cn Edge& y){return x.x>y.x;}
I bool cmp2(Cn Que& x,Cn Que& y){return x.x>y.x;}
class TreeArray{
    private:
        int c[N];
        #define lowbit(x) (x&(-x))
    public:
        I void U(CI x,CI y){RI i;for(i=x;i<=n;i+=lowbit(i)) c[i]+=y;}
        I int Q(CI x){RI i,S=0;for(i=x;i;i-=lowbit(i)) S+=c[i];return S;}
}T;
int main(){
    RI i,j,l,r;for(read(n),read(m),i=1;i<n;i++) read(l),read(r),e[i]=(Edge){min(min(l,r),i),max(max(l,r),i)};
    for(i=1;i<=m;i++) read(q[i].x),read(q[i].y),q[i].id=i;
    for(j=1,sort(e+1,e+n,cmp),sort(q+1,q+m+1,cmp2),i=1;i<=m;i++){
        W(j<n&&e[j].x>=q[i].x) T.U(e[j].y,1),j++;
        Ans[q[i].id]=q[i].y-q[i].x+1-T.Q(q[i].y);
    }for(i=1;i<=m;i++) write(Ans[i]),pc('\n');
    return 0;
}