【テーマ】

トランスファゲート
タイトルの説明:
IcePrincess_1968とIcePrince_1968年に成長して王に協力し始めました1968年に国内の事物を管理する.
IcePrincess_1968とIcePrince_1968年に静かで遠い王国に住んでいます:IceKingdom--雪の聖域.漂雪聖域にはn n nの町があり、番号1,2,3,..,n 1,2,3,...,n 1,2,3,...,n.一部の町の間には道路があり、任意の2点の間に1つの経路しかありません.雪が舞う聖域は景色が美しいが、気候はあまりよくない.IcePrince_によると1968年の気候探査機では、将来q q場の吹雪が発生する.吹雪ごとに2つの整数l i,r i l_を使用できます.i,r_i li,riは、この吹雪の後、番号だけが[  l i  ,  r i  [\;l_i\;,\;r_i\;] [li,ri]の都市は吹雪の影響を受けていない.
吹雪の影響で王国の農業生産案を迅速に確定することは非常に重要なことだ.IceKing_1968年には、農業生産地域は極大連通塊であり、各ノードが吹雪の影響を受けていないことを満たすべきだと考えている.ここで、極大連通ブロックの定義は、この点セットに属さない吹雪の影響を受けない点がこの連通ブロックと連通することはない.
IcePrincess_1968年には、吹雪のたびに王国がどれだけの農業生産地域を持つことができるかを計算する責任がある.ここは吹雪が独立するたびに、つまり吹雪が過ぎるたびに、町が再び活気を取り戻すまで、次の吹雪が来ることに注意してください.
前述したように、IcePrincess_1968年は文学が得意ですが、コンピューターが苦手なので、手伝ってください.
入力形式:
1行目は2つの正の整数n,q n,q n,qを含み,IceKingdomの町の個数と吹雪の回数を表す.
2番目の2行目からn番目のn行目まで、各行の2つの正の整数x,y x,y x,yは、都市x x xと都市y y yの間に道路があることを示す.
n+1 n+1 n+1~n+q n+q n+q n+q行目、各行に2つの正の整数l i,r i l_i,r_i li,ri,吹雪を記述し,問題面で述べたような意味を持つ.
出力フォーマット:
出力ファイルはq q行,i i i行目はi i i場吹雪後の農業生産地域の個数を示す.
サンプルデータ:
入力4 3 3 1 2 2 3 4 4 1 2 3 4
出力1 1 1 2
ヒント:
【入出力サンプル1 1 1解釈】
1回目の問い合わせでは、(1,2)(1,2)(1,2)1つの連通ブロックしかありません.
2回目の問い合わせでは、(1,2,3)(1,2,3)(1,2,3)の1つの連通ブロックしかありません.
3回目の問い合わせでは、3 3 3と4 4の2つの連通ブロックがあります.
【データ規模】
30%30%30%のデータ:n≦100 nle 100 n≦100,q≦100 qle 100 q≦100;
50%50%50%のデータ:n≦2,000 nle 2000 n≦2000,q≦2,000 qle 2000 q≦2000;
100%100%100%データ:n≦200,000 nle 200000 n≦200000,q≦200,000 qle 200000 q≦200000,すべての吹雪に対してl i≦r i l_i\le r_i li​≤ri​.

【分析】

実際、私たちはこの問題を変換することができます.
1つのエッジ(u,v)(u,v)(u,v)について、u uとv vの2つの点が影響されなければ、(u,v)(u,v)(u,v)(u,v)を良いエッジと呼ぶ.
それぞれの良い辺は両端点がある連通ブロックを接続し、総連通ブロック数−1−1−1とすることができる.
そこでn u m numの良い辺があれば,[  l i  ,  r i  ][\;l_i\;,\;r_i\;] [li,ri]の答えはr i−l i+1−n u m r_である.i-l_i+1-num ri​−li​+1−num.
1つのエッジ(u,v)(u,v)(u,v)について、uでは、私たちはl i≦uでは、質問をオフラインにして、木の配列で解決すればいいです.

【コード】

#include
#include
#include
#include
#define N 200005
#define lowbit(x) (x&-x)
#define Pair pair
using namespace std;
vector<int>E[N];
vector<Pair>Q[N];
int n,q,bit[N],ans[N];
void add(int i,int x)
{
	for(;i<=n;i+=lowbit(i))  bit[i]+=x;
}
int query(int i)
{
	int ans=0;
	for(;i;i-=lowbit(i))  ans+=bit[i];
	return ans;
}
int main()
{
	int x,y,i,j;
	scanf("%d%d",&n,&q);
	for(i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		if(x>y)  swap(x,y);
		E[y].push_back(x);
		add(x,1);
	}
	for(i=1;i<=q;++i)
	{
		scanf("%d%d",&x,&y);
		Q[y].push_back(make_pair(x,i));
	}
	for(i=n;i;--i)
	{
		for(j=0;j<Q[i].size();++j)
		{
			int sum=query(i)-query(Q[i][j].first-1);
			ans[Q[i][j].second]=(i-Q[i][j].first+1)-sum;
		}
		for(j=0;j<E[i].size();++j)  add(E[i][j],-1);
	}
	for(i=1;i<=q;++i)
	  printf("%d
",ans[i]);
	return 0;
}