点我看题目 题意： 给出一颗n个点的树 结点编号1-n。 给出一个二元组[l,r] 定义一个结点为好结点 当且仅当 其编号 i 满足 l< i < r 时 i结点为好结点。 两个相邻好结点之间的边为好边。 现在有Q次询问 每次询问给出[l,r] 对于每次询问 求出由好边链接的连通块的个数。
解题思路： 最容易想到就是对每次询问进行一遍DFS，找坏边，然后求连通块的个数， 总复杂度为O(nq) 之后想到 其实连通块的个数等于好点个数减去好边个数。 然后询问很像线段树的询问，联想到区间求和问题。 把所有边全部放在一个一维坐标轴上，那么问题可以转化为两端点都在[l,r] 范围内的边有多少条。 先得到一个最暴力的算法 每次询问 暴力遍历所有边，找其中符合条件的边。 复杂度同样为O(nq) 在想如何使用线段树去优化。 一开始就把所有点都加到线段树里面去，然后再查询的做法很容易可以证明是行不通的。情况太多。 想如何化简问题的情况， 根据以前的题目，联想到排序后进行离线处理求结果。 对于询问和边 都用右端点为关键字排序。 然后在询问过程中添加符合右端点小于询问 r的边， 将之左端点l加入到线段树中。 这样 复杂度就降到了O(qlogn) 然后用线段树写老报错 ，改成树状数组就A了
#include<bits/stdc++.h> #define LL long long #define INF 0x3f3f3f3f using namespace std; const int MAX=(1e5+10)*2; int tree[MAX],n=MAX; void add(int x,int num) { for(;x<=n;x+=x&-x) tree[x]+=num; } int sum(int x) { int answer =0; for(;x>0;x-=x&-x) answer+=tree[x]; return answer; } class Node{ public: int l,r,id; bool operator <(const Node &b) const { return r<b.r; } } ; Node node1[MAX]; Node node2[MAX]; int ans[MAX]; int main(){ int T; scanf("%d",&T); while(T--){ int n,q; memset(tree,0,sizeof tree); scanf("%d %d",&n,&q); for(int i=1;i<n;i++){ scanf("%d %d",&node1[i].l,&node1[i].r); if(node1[i].l>node1[i].r) swap(node1[i].l,node1[i].r); } for(int i=1;i<=q;i++){ scanf("%d %d",&node2[i].l,&node2[i].r); node2[i].id=i; } sort(node1+1,node1+n); sort(node2+1,node2+q+1); int tot=1; for(int i=1;i<=q;i++){ int l=node2[i].l,r=node2[i].r; //cout<<l<<","<<r<<","<<node2[i].id<<endl; while(node1[tot].r<=r && tot<n){ add(node1[tot].l,1); //cout<<"up"<<node1[tot].l<<" "<<node1[tot].r<<endl; tot++; } int sums=sum(r)-sum(l-1); ans[node2[i].id]=(r-l+1-sums); } for(int i=1;i<=q;i++){ printf("%d\n",ans[i]); } } }