loj2049 「HNOI2016」网络

好像复杂度来说不是正解……不加谜之优化（下叙）能被loj上的加强数据卡
#include <algorithm>

#include <iostream>

#include <cstdio>

#include <vector>

using namespace std;

int n, m, hea[100005], cnt, uu[200005], fa[100005], siz[100005], son[100005], idx;

int dfn[100005], top[100005], opt, vv[200005], ww[200005], dep[100005], xx, ans;

struct Edge{

	int too, nxt;

}edge[200005], lian[100005];

struct SGTNode{

	vector<int> vec1, vec2;

	void insert(int x){

		vec1.push_back(x);

		push_heap(vec1.begin(), vec1.end());

	}

	void shanchu(int x){

		vec2.push_back(x);

		push_heap(vec2.begin(), vec2.end());

	}

	int getTop(){

		while(true){

			if(!vec1.size())	return -1;

			if(!vec2.size())	return vec1[0];

			if(vec1[0]==vec2[0]){

				pop_heap(vec1.begin(), vec1.end());

				vec1.pop_back();

				pop_heap(vec2.begin(), vec2.end());

				vec2.pop_back();

			}

			else	return vec1[0];

		}

	}

};

struct SGT{

	SGTNode nd[400005];

	void update(int o, int l, int r, int x, int y, int w){

		if(l>=x && r<=y){

			if(opt==0)	nd[o].insert(w);

			else	nd[o].shanchu(w);

		}

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			if(x<=mid)	update(lson, l, mid, x, y, w);

			if(mid<y)	update(rson, mid+1, r, x, y, w);

		}

	}

	void query(int o, int l, int r, int x){

		ans = max(ans, nd[o].getTop());

		if(l==r)	;

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			if(x<=mid)	query(lson, l, mid, x);

			else	query(rson, mid+1, r, x);

		}

	}

}sgt;

bool cmp(const Edge &u, const Edge &v){

	return u.too<v.too;

}

void add_edge(int fro, int too){

	edge[++cnt].nxt = hea[fro];

	edge[cnt].too = too;

	hea[fro] = cnt;

}

void dfs1(int x, int f){

	fa[x] = f;

	dep[x] = dep[f] + 1;

	siz[x] = 1;

	int maxSon=-1;

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(t!=f){

			dfs1(t, x);

			siz[x] += siz[t];

			if(siz[t]>=maxSon){//就是这里，要写\geq……

				maxSon = siz[t];

				son[x] = t;

			}

		}

	}

}

void dfs2(int x, int topf){

	dfn[x] = ++idx;

	top[x] = topf;

	if(!son[x])	return ;

	dfs2(son[x], topf);

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(t!=fa[x] && t!=son[x])

			dfs2(t, t);

	}

}

void rangeUpdate(int u, int v, int w){

	int faq=0;

	while(top[u]!=top[v]){

		if(dep[top[u]]<dep[top[v]])	swap(u, v);

		lian[++faq] = (Edge){dfn[top[u]], dfn[u]};

		u = fa[top[u]];

	}

	if(dep[u]>dep[v])	swap(u, v);

	lian[++faq] = (Edge){dfn[u], dfn[v]};

	sort(lian+1, lian+1+faq, cmp);

	int lst=0;

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

		if(lst+1<=lian[i].too-1)

			sgt.update(1, 1, n, lst+1, lian[i].too-1, w);

		lst = lian[i].nxt;

	}

	if(lst+1<=n)

		sgt.update(1, 1, n, lst+1, n, w);

}

int main(){

	cin>>n>>m;

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

		scanf("%d %d", &xx, &ans);

		add_edge(xx, ans);

		add_edge(ans, xx);

	}

	dfs1(1, 0);

	dfs2(1, 1);

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

		scanf("%d", &opt);

		if(opt==0){

			scanf("%d %d %d", &uu[i], &vv[i], &ww[i]);

			rangeUpdate(uu[i], vv[i], ww[i]);

		}

		else if(opt==1){

			scanf("%d", &xx);

			rangeUpdate(uu[xx], vv[xx], ww[xx]);

		}

		else{

			scanf("%d", &xx);

			ans = -1;

			sgt.query(1, 1, n, dfn[xx]);

			printf("%d\n", ans);

		}

	}

	return 0;

}
巴特西

loj2049 「HNOI2016」网络

最新文章

热门文章
