[bzoj1103][POI2007]大都市meg_dfs序_树状数组

2021-07-11 09:06

阅读：629

标签：add line fine pos tin 大都市 lowbit clu oid

大都市meg bzoj-1103 POI-2007

题目大意：给定一颗n个点的树，m次操作。将一条路的边权更改成0；查询一个点到根节点的点权和。开始的时候所有边的边权都是1。

注释：$1\le n,m\le 2.5\cdot 10^5$。

想法：我们先拉出dfs序。其实严格来讲是出栈入栈序，就是每个点在序上出现两次的那个。

开始的时候入栈时的点权是1，出栈是-1。修改就是把出栈入栈都改成0。然后用树状数组查询前缀和即可。

最后，附上丑陋的代码... ...

#include 
#include 
#include 
#include 
#define N 250010 
using namespace std;
int tree[N=1;i-=lowbit(i))
	{
		// puts("query");
		ans+=tree[i];
	}
	return ans;
}
inline void add(int x,int y)
{
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void dfs(int pos,int fa)
{
	// if(a[pos].x) puts("FUCK");
	dic[++cnt]=pos;
	// cnt++;
	val[cnt]=1;
	a[pos].x=cnt;
	for(int i=head[pos];i;i=nxt[i])
	{
		if(to[i]==fa) continue;
		dfs(to[i],pos);
	}
	dic[++cnt]=pos;
	// cnt++;
	val[cnt]=-1;
	a[pos].y=cnt;
}
int main()
{
	int n; cin >> n ;
	int x,y;
	for(int i=1;i> m ;
	char opt[10];
	// for(int i=1;iy) swap(x,y);
			fix(a[y].x,-1);
			fix(a[y].y,1);
		}
		else
		{
			scanf("%d",&x);
			// printf("%d\n",query(3));
			printf("%d\n",query(a[x].x));
		}
	}
	return 0;
}

小结：简单题。

[bzoj1103][POI2007]大都市meg_dfs序_树状数组

标签：add line fine pos tin 大都市 lowbit clu oid

原文地址：https://www.cnblogs.com/ShuraK/p/9551545.html

上一篇：python 面向对象（二）

下一篇：spring mvc 小demo

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[bzoj1103][POI2007]大都市meg_dfs序_树状数组
文章链接：http://soscw.com/index.php/essay/103637.html

亲，登录后才可以留言！

[bzoj1103][POI2007]大都市meg_dfs序_树状数组

评论

热门文章

推荐文章

最新文章

置顶文章