亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

【POI 2007】Megalopolis大都市(meg)

系統 1826 0

  八中鏈接 http://www.zybbs.org/JudgeOnline/problem.php?id=1103

  原題鏈接 http://main.edu.pl/en/archive/oi/14/meg

  題目大意:給你一棵樹(仔細揣摩題目描述,是樹),邊有權(1或0),每個詢問問從1到x的路徑上權值和是多少。

  看完我就在想LCT亂搞……然后發現LCT有點高射炮打蚊子了。后來發現這個題可以線性維護DFS序列來做,用線段樹。

  (PS:其實我寫樹狀數組…………)

      #include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#define mn 250002

#define lowbit(x) (x)&(-x)

using namespace std;



pair<int,int> pos[mn];

int n,m,a,b,node=0,s[mn*2];

char sym[2];

bool vis[mn];



struct EDGE{

	int pnt;

	EDGE *pre;

	EDGE(){}

	EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}

}Edge[mn*2],*SP=Edge,*edge[mn];



inline void addedge(int a,int b){

	edge[a]=new(++SP)EDGE(b,edge[a]);

	edge[b]=new(++SP)EDGE(a,edge[b]);

}



void Modify(int x,int val){

	while(x<=n) s[x]+=val,x+=lowbit(x);

}



int Query(int x){

	int sum=0;

	while(x>0) sum+=s[x],x-=lowbit(x);

	return sum;

}



void dfs(int x){

	pos[x].first=++node;

	Modify(node,1);

	vis[x]=true;

	for(EDGE *j=edge[x];j;j=j->pre)

		if(!vis[j->pnt]) dfs(j->pnt);

	pos[x].second=++node;

	Modify(node,-1);

}



int main(){

	scanf("%d",&n);

	for(int i=1;i<n;i++){

		scanf("%d%d",&a,&b);

		addedge(a,b);

	}

	n<<=1;

	dfs(1);

	scanf("%d",&m);

	while(m){

		scanf("%s",sym);

		if(sym[0]=='W'){

			scanf("%d",&a);

			printf("%d\n",Query(pos[a].first)-1);

			m--;

		}else{

			scanf("%d%d",&a,&b);

			Modify(pos[b].first,-1);

			Modify(pos[b].second,1);

		}

	}

	return 0;

}


    

【POI 2007】Megalopolis大都市(meg)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 欧美资源站 | 在线色片| 久久久国产精品视频 | 午夜国产精品理论片久久影院 | 久久亚洲国产成人影院 | 亚洲精品aⅴ一区二区三区 亚洲精品ccc | a级毛片在线观看 | 成人免费视频网 | 91大片| 精品欧美成人bd高清在线观看 | 四虎黄网 | 国产在线观看精品香蕉v区 国产在线观看美女福利精 国产在线观看午夜不卡 | 久久国产综合 | 亚洲第一区视频在线观看 | 国产精品午夜免费福利视频 | 久久奇米 | 亚洲视频一二三 | 欧美一级毛片欧美毛片视频 | 久久精品一区二区三区中文字幕 | 99精品国产高清自在线看超 | 欧洲成人在线 | 国产欧美综合在线一区二区三区 | 97爱爱爱 | 国产欧美一区二区久久 | 欧美中文字幕在线看 | 日韩亚洲欧美在线观看 | 国产99在线 | 亚洲 | 天天干夜夜 | 精品国产一区二区三区久久 | 亚洲国产成人九九综合 | 色综合久久88一加勒比 | 国产精品亚洲欧美一区麻豆 | 777奇米影视久久激情日韩欧美 | 天天干天天弄 | a毛片在线播放 | 国内精品久久久久影院网站 | 天天躁夜夜躁狂狂躁综合 | 91在线免费视频观看 | 九九精品视频在线免费观看 | 999热在线精品观看全部 | 超级碰碰青草久热国产 |