Submission #3799567


Source Code Expand

Copy
#include<bits/stdc++.h>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 2e5+5;

int n;
struct edge{
	int x,nxt;
}e[N*2];
int h[N],tot;

void inse(int x,int y){e[++tot].x=y;e[tot].nxt=h[x];h[x]=tot;}

bool vis[N];
int mx[N];
int fa[N];
vector<int>key[N];
int Fa[N];
int val[N];

void dfs(int x){
	vis[x]=1;
	for(int p=h[x];p;p=e[p].nxt)
	if (!vis[e[p].x]){
		Fa[e[p].x]=x;
		mx[e[p].x]=max(mx[x],x);
		dfs(e[p].x);
	}
}

int siz[N];

int getfather(int x){return fa[x]==x?x:fa[x]=getfather(fa[x]);}

int ans[N];
int sta[N],top,pos[N];

void getans(int x){
	sta[pos[x]=++top]=x;
	if (x!=1)ans[x]=ans[x]+ans[mx[x]]-val[sta[pos[mx[x]]+1]];
	vis[x]=1;
	for(int p=h[x];p;p=e[p].nxt)
	if (!vis[e[p].x])getans(e[p].x);
	top--;
}

int main(){
	n=get();
	fo(i,2,n){
		int x=get(),y=get();
		inse(x,y);
		inse(y,x);
	}
	dfs(1);
	fo(i,1,n)fa[i]=i,siz[i]=1;
	siz[1]=0;
	fo(i,2,n)key[mx[i]].push_back(i);
	fo(i,1,n){
		for(auto x:key[i]){
			if (x<i)ans[x]=siz[getfather(x)];
			else{
				for(int p=h[x];p;p=e[p].nxt)
				if (e[p].x<i){
					int v=siz[getfather(e[p].x)];
					if (Fa[e[p].x]==x)val[e[p].x]=v;
					ans[x]+=v;
				}
				ans[x]++;
			}
		}
		for(int p=h[i];p;p=e[p].nxt)
		if (e[p].x<i){
			int fx=getfather(i),fy=getfather(e[p].x);
			fa[fx]=fy;
			siz[fy]+=siz[fx];
		}
	}
	fo(i,1,n)vis[i]=0;
	getans(1);
	fo(i,2,n)printf("%d%c",ans[i],i==n?'\n':' ');
	return 0;
}

Submission Info

Submission Time
Task E - Wandering TKHS
User samjia2000
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 1824 Byte
Status AC
Exec Time 89 ms
Memory 23796 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 3
AC × 32
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt
All sample01.txt, sample02.txt, sample03.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, sample01.txt, sample02.txt, sample03.txt
Case Name Status Exec Time Memory
in01.txt AC 78 ms 16760 KB
in02.txt AC 79 ms 16628 KB
in03.txt AC 77 ms 16636 KB
in04.txt AC 75 ms 16756 KB
in05.txt AC 81 ms 16888 KB
in06.txt AC 77 ms 16632 KB
in07.txt AC 4 ms 10496 KB
in08.txt AC 4 ms 10496 KB
in09.txt AC 4 ms 10496 KB
in10.txt AC 4 ms 10496 KB
in11.txt AC 4 ms 10496 KB
in12.txt AC 5 ms 10624 KB
in13.txt AC 5 ms 10624 KB
in14.txt AC 5 ms 10624 KB
in15.txt AC 5 ms 10496 KB
in16.txt AC 5 ms 10624 KB
in17.txt AC 70 ms 20600 KB
in18.txt AC 40 ms 15860 KB
in19.txt AC 45 ms 15860 KB
in20.txt AC 53 ms 23796 KB
in21.txt AC 89 ms 18048 KB
in22.txt AC 58 ms 17408 KB
in23.txt AC 59 ms 17436 KB
in24.txt AC 72 ms 17560 KB
in25.txt AC 72 ms 17396 KB
in26.txt AC 4 ms 10496 KB
sample01.txt AC 4 ms 10496 KB
sample02.txt AC 4 ms 10496 KB
sample03.txt AC 4 ms 10496 KB