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

Hdu 4916 Count on the path

系統 2372 0

意甲冠軍:鑒于一棵樹的頂點標簽為連續1~n,不是每個網上查詢a-b最小的圓點標簽路徑

這題想了好久,如果1為根節點。

首先如果a-b只是根節點1。答案一定是1。

否則我們用fa[i]表示i節點的父親,belong[i]表示i節點祖先是belong[i],且belong[i]是根節點兒子。這樣我們能夠預處理出ans[i]表示在belong[i]這顆子樹中除去i到根節點的路徑中最小的值。統計答案就可以。

討論時需注意一些細節,首先處理出每一個節點的最小值和次小值,分別來源于它的兩個子樹。不包含節點本身。統計ans[i]的時候要在belong[i]中討論且先統計不包含i本身子樹的部分,顯然ans[i]能夠等于ans[fa[i]]。假設以i的子樹(包含節點)的最小值和fa[i]的最小值相等,顯然ans[i]能夠等于fa[i]的次小值,由于i和fa[i]次小值節點不在一顆子樹上; 假設以i的子樹(包含節點)的最小值和fa[i]的次小值相等,顯然ans[i]能夠等于fa[i]的最小值。最后再比較ans[i]和i本身子樹最小值來更新ans[i]。

統計出ans[i]后每次詢問O(1)回答就可以。

代碼 https://github.com/mlz000/hdu/blob/master/4916(%E6%A0%91%E4%B8%8A%E5%A5%BD%E9%A2%98).cpp

      #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000005,inf=1e9;
int n,q,tot,min3,belong[N],Q[N],head[N],next[N<<1],to[N<<1],fa[N],ans[N];
pair<int,int>a[N];
#define mp make_pair 
void add(int u,int v){
	to[++tot]=v;
	next[tot]=head[u];
	head[u]=tot;
}
int ask(int x,int y){
	if(x>y)	swap(x,y);
	if(x==1 || y==1){
		if(x==1 && y==1)	return a[1].first;
		if(min(belong[y],ans[belong[y]])!=a[1].first)	return	a[1].first;
		return min(a[1].second,ans[y]);
	}
	else{
		if(belong[x]==belong[y])	return 1;
		int tmp1=min(belong[x],a[belong[x]].first),tmp2=min(belong[y],a[belong[y]].first);
		if(min(tmp1,tmp2)!=a[1].first)	return a[1].first;
		int now=0;
		if(tmp1!=a[1].second && tmp2!=a[1].second)	 now=a[1].second;
		else now=min3;
		now=min(now,min(ans[x],ans[y]));
		return now;
	}
}
int main(){
	while(~scanf("%d%d",&n,&q)){
		int last=0;
		tot=0;
		memset(head,0,sizeof(head));
		for(int i=1,x,y;i<n;++i){
			scanf("%d%d",&x,&y);
			add(x,y);
			add(y,x);
		}
		Q[1]=1;
		for(int h=1,r=1;h<=r;++h){
			int now=Q[h];
			for(int i=head[now];i;i=next[i]){
				if(to[i]==fa[now])	continue;
				if(belong[now])	belong[to[i]]=belong[now];
				else belong[to[i]]=to[i];
				fa[to[i]]=now;
				Q[++r]=to[i];
			}
		}
		for(int i=1;i<=n;++i)	a[i]=mp(inf,inf);
		for(int i=n;i>=1;--i){
			int now=Q[i];
			int tmp=min(now,a[now].first);
			int father=fa[now];
			if(tmp<a[father].second){
				a[father].second=tmp;
				if(a[father].second<a[father].first)	swap(a[father].first,a[father].second);
			}
		}
		min3=inf;
		for(int i=head[1];i;i=next[i]){
			int now=min(to[i],a[to[i]].first);
			if(now!=a[1].first && now!=a[1].second)	min3=min(min3,now);
		}
		for(int i=2;i<=n;++i){
			int minnow=min(Q[i],a[Q[i]].first);
			int father=fa[Q[i]];
			if(father!=1){
				ans[Q[i]]=ans[father];
				if(minnow==a[father].first)	ans[Q[i]]=min(ans[Q[i]],a[father].second);
				else ans[Q[i]]=min(ans[Q[i]],a[father].first);
			}
			else ans[Q[i]]=inf;
		}
		for(int i=2;i<=n;++i)	ans[i]=min(ans[i],a[i].first);
		while(q--){
			int x,y;
			scanf("%d%d",&x,&y);
			x=x^last;
			y=y^last;
			last=ask(x,y);
			printf("%d\n",last);
		}
	}
	return 0;
}

    


版權聲明:本文博客原創文章。博客,未經同意,不得轉載。

Hdu 4916 Count on the path


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

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

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

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 99影视在线视频免费观看 | 富二代啪啪精品网站 | 亚洲免费视频在线观看 | 国产成人午夜性视频影院 | 在线a人片免费观看国产 | 中文字幕无线码中文字幕免费 | 日本一区二区三区高清福利视频 | 欧美黑大粗硬毛片视频 | 国产欧美日本亚洲精品五区 | 久久久精品久久久久久 | 久久99精品一久久久久久 | 一级aa 毛片高清免费看 | 国内精品自在欧美一区 | 四虎影视在线免费观看 | 久久天天躁日日躁狠狠躁 | 伊人久久大香线蕉综合bd高清 | 日韩成人免费aa在线看 | 国产福利91精品一区二区 | 亚洲精品久久九九热 | 免费一级特黄视频 | 性久久久久 | 成人小视频在线 | 亚洲第一视频在线播放 | 98色花堂国产精品首页 | 在线看污网站 | 四虎精品视频 | 欧美天天性影院 | 久久久亚洲国产精品主播 | 五月色婷婷综合激情免费视频 | 久久噜噜久久久精品66 | 最新91视频| 久久精品国产亚洲黑森林 | 999热成人精品国产免 | 国产高清对白国产露脸91 | 一区二区三区久久 | 久久中文字幕2021精品 | 在线 v亚洲 v欧美v 专区 | 久久视频这里只有精品35 | 日本福利片国产午夜久久 | 色婷婷久久综合中文久久一本` | 正在播放国产乱子伦视频 |