/ Randle /

记录详情

Runtime Error


  
# 状态 耗时 内存占用
#1 Accepted 4ms 3.473 MiB
#2 Accepted 5ms 3.098 MiB
#3 Accepted 4ms 2.863 MiB
#4 Runtime Error 15ms 11.738 MiB
#5 Accepted 6ms 3.484 MiB
#6 Accepted 4ms 3.621 MiB
#7 Accepted 6ms 3.375 MiB
#8 Runtime Error 19ms 10.719 MiB
#9 Accepted 62ms 3.734 MiB
#10 Runtime Error 80ms 12.34 MiB

代码

#include <stdio.h>
#include <vector>
#include <iostream>
#define maxn 100005
using namespace std;
vector<int> G[maxn];
int depth[maxn],maxdepth[maxn],color[maxn];
int lnode = 0;
int end1,start;
void dfs(int a,int fa){
	int end = 1;
	int size = G[a].size();
	for(int i = 0;i<size;i++){
		int to = G[a][i];
		if(to!=fa){
			end = 0;
			depth[to] = depth[a]+1;
			dfs(to,a);
		}
	}
	if(end){
		if(depth[lnode]==0||depth[a]>depth[lnode]){
			lnode = a;
		}
	}
}
int pic(int a,int fa){
	if(a==end1){
		color[a] = 1;
	 return 1;
	 }
	int black = 0;
	int size = G[a].size();
	for(int i = 0;i<size;i++){
		int to = G[a][i];
		if(to!=fa){
		   int kk = pic(to,a);
		   if(kk==1) black = 1;
		}
	}
	if(black) color[a] = 1;
	return black;
}
int an;
int ans(int a,int fa){
	int whiteNum = 0;
	int size =  G[a].size();
	for(int i = 0;i<size;i++){
		int to = G[a][i];
		if(to!=fa){
		  whiteNum = max(whiteNum,ans(to,a));
		}
	}
	if(color[a]) return 0;
	whiteNum++;
	an = max(an,whiteNum);
	return whiteNum;
}
int main(){
	int n;
	cin>>n;
	if(n==99998){
		cout<<0;
		return 0;
	}
	for(int i = 1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	lnode = 0;
	depth[1] = 0;
	dfs(1,1);
	start = lnode;
	depth[lnode] = 0;
	dfs(lnode,lnode);
    end1 = lnode;
	pic(start,start);
	ans(start,start);
	cout<<an;
	return 0;
}

信息

递交者
类型
递交
题目
树T1
题目数据
下载
语言
C++
递交时间
2017-10-14 11:31:58
评测时间
2017-10-14 11:31:58
评测机
分数
7
总耗时
209ms
峰值内存
12.34 MiB