ZOJ 4008 Yet Another Tree Query Problem

发表于 | 分类于 | 浏览 次

题意

给一颗树，q个询问，每个询问求节点标号$[l,r]$之间的节点组成的连通块的个数。

题解

首先这个图是一棵树，$[l,r]$连通块的个数就是$r-l+1-e$($e$为两点标号都在$[l,r]$的边的个数)
把每条边编号大的点放入树状数组。
然后把询问按$l$从小到大排序。
之后从1到n枚举左端点，每轮循环最后把左端点在$i$的边从树状数组中删除。这样树状数组中的边的左端点总是大于$i$，因此当i枚举到每个询问的$l$时，sum(r)就是两点标号都在$[l,r]$的边的个数)

总结

看到图是树一定要想到树的特点和性质，这道题树状数组依然是应用到了之前总结的树状数组解决两个不等式限制问题，但自己还是没有想到。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include "iostream"
#include <cmath>
#include <vector>
#include "set"
using namespace std;
#define FOP freopen("input.txt","r",stdin)
#define Met(x,y) memset(x,y,sizeof x)
typedef long long ll;
const ll INF = 1e18;
const ll MAXN =2e5+100;
const ll MOD = 1e9+7;

ll BIT[MAXN],n;
ll Lowbit(ll x)  // 2^k
{
    return x&(-x);
}
void update(ll i, ll x)//i点增量为x
{
    while(i <= n)
    {
        BIT[i] += x;
        i += Lowbit(i);
    }
}
ll sum(ll x)//区间求和 [1,x]
{
    ll sum=0;
    while(x>0)
    {
        sum+=BIT[x];
        x-=Lowbit(x);
    }
    return sum;
}
vector<ll> lp[MAXN];
void init()
{
    for(int i=0;i<MAXN;++i)
        lp[i].clear();
    Met(BIT,0);
}
struct Ele{
    ll l,r,id;
    bool operator < (const Ele &a)const{
        return l<a.l;
    }
}que[MAXN];
ll ans[MAXN];
int main(int argc, char const *argv[]) {
    ll m;
    ll T_T;
    cin>>T_T;
    while(T_T--)
    {
        init();
        cin>>n>>m;
        for(int i=1;i<n;++i)
        {
            ll u,v;
            scanf("%lld%lld",&u,&v);
            update(max(v,u),1);
            lp[min(u,v)].push_back(max(u,v));
        }
        for(int i=0;i<m;++i)
        {
            scanf("%lld%lld",&que[i].l,&que[i].r);
            que[i].id=i;
        }
        sort(que,que+m);
        ll cur=0;
        for(int i=1;i<=n;++i)
        {
            while (cur<m && que[cur].l==i) {
                ans[que[cur].id]=que[cur].r-que[cur].l+1-sum(que[cur].r);
                cur++;
            }
            for(int j=0;j<lp[i].size();++j)
                update(lp[i][j],-1);
        }
        for(int i=0;i<m;++i)
            printf("%lld\n", ans[i]);
    }
    return 0;
}