【Codeforces 708C】Centroids

题目传送门:http://codeforces.com/problemset/problem/708/C

我是函数式线段树+出栈入栈序的做法(其实一个RMQ即可)
但这题可以O(n)DP!记录子树中,最大的,不超过n/2的值是多少

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 800000+9;
const int M = 20000000;
const int INF = 1000000000;

int n,tot[N],ls[N],sig,rs[N],head[N],to[N],nxt[N],vex[N*2];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

namespace Chair_Tree{
	#define CT Chair_Tree
	int sum[M][2],ch[M][2],cnt,root[N],ans_tmp;
	
	void Add(int p, int &w, int l, int r, int pos, int ty) {
		w = ++cnt; ch[w][0] = ch[p][0]; ch[w][1] = ch[p][1]; 
		sum[w][0] = sum[p][0]; sum[w][1] = sum[p][1]; sum[w][ty]++;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (pos < mid) Add(ch[p][0],ch[w][0],l,mid-1,pos,ty);
			else Add(ch[p][1],ch[w][1],mid,r,pos,ty);
		}
	} 
	
	inline void modify(int i, int val) {
		if (val > 0) Add(root[i-1],root[i],1,n,val,1);
		else Add(root[i-1],root[i],1,n,-val,0);
	}
	
	void query(int w, int l, int r, int L, int R, int f, int ty){
		if (L <= l && r <= R) ans_tmp += sum[w][ty]*f;
		else {
			int mid = l + r + 1 >> 1;
			if (L < mid) query(ch[w][0],l,mid-1,L,R,f,ty);
			if (R >= mid) query(ch[w][1],mid,r,L,R,f,ty);
		}
	}
	
	inline int query(int l, int r, int L, int R,int ty) {
		if (l > r) return false;
		ans_tmp = 0;
		query(root[l-1],1,n,L,R,-1,ty);
		query(root[r],1,n,L,R,1,ty);
		return ans_tmp;
	}
	
	inline void Merge(){
		for (int i=1;i<=cnt;i++) 
			sum[i][0] = sum[i][1] - sum[i][0];
	}
};

void DFS(int w, int f) {
	tot[w] = 1; ls[w] = ++sig; 
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f)
		DFS(to[i],w), tot[w] += tot[to[i]];
	rs[w] = ++sig; 
	vex[ls[w]] = tot[w];
	vex[rs[w]] = -tot[w];
}

inline void AddEdge(int a, int b) {
	static int T = 0;
	to[++T] = b; nxt[T] = head[a]; head[a] = T;
	to[++T] = a; nxt[T] = head[b]; head[b] = T;
}

inline bool judge(int w) {
	int MX = 0, vx = 0, MN, ty, sta;
	for (int i=head[w];i;i=nxt[i]) 
		if (ls[w] < ls[to[i]] && ls[to[i]] <= rs[w]) {if (MX < tot[to[i]]) MX = tot[to[i]], vx = to[i], ty = 0;} 
		else {int tmp = n - tot[w]; if (MX < tmp) MX = tmp, vx = to[i], ty = 1;}
	if (MX <= n/2) return 1;
	else {
		sta = n/2;
		MN = MX-n/2;
		if (!ty) return CT::query(ls[vx],rs[vx],MN,sta,1);
		else {
			int tmp = CT::query(1,ls[w]-1,MN,sta,1) + CT::query(rs[w]+1,n*2,MN,sta,1);
			tmp -= CT::query(1,ls[w]-1,MN,sta,0); MN = n - MN; sta = n - sta; swap(MN,sta);
			tmp += CT::query(2,ls[w],MN,sta,0);
			return tmp;
		}
	}
}

int main(){
	n = read(); 
	for (int i=1;i<n;i++) AddEdge(read(),read()); DFS(1,1);
	for (int i=1;i<=n*2;i++) CT::modify(i,vex[i]); CT::Merge();
	for (int i=1;i<=n;i++) printf("%d ",judge(i));
	return 0;
}

3 thoughts to “【Codeforces 708C】Centroids”

  1. 来毒瘤一下退役选手QwQ(不知大学生活可好?)
    这道题其实可以直接贪心。以重心为根建树,然后对于每个点考虑能否把根的其他的最大子树接过来变成重心。
    瞎维护一下就好了。

  2. I keep listening to the news broadcast lecture about getting boundless online grant applications so I have been looking around for the finest site to get one. Could you tell me please, where could i get some?

  3. Magnificent items from you, man. I’ve have in mind your stuff prior to and you are just too great. I really like what you have obtained right here, really like what you are stating and the best way wherein you say it. You make it entertaining and you still take care of to stay it sensible. I can not wait to read far more from you. That is really a tremendous website.

Leave a Reply

Your email address will not be published. Required fields are marked *