当前位置：/p/1331

P1331 sdlwwlp分饼

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

sdlwwlp要和WD分一张大大大饼，奇怪的是这张饼竟然是树状的（@_@，像风铃一样)，每个“节点"都像一张比较小的饼,中间用线穿了起来，形成了一张严格的树状图，现在他们两个为了公平起见，需要切断一条边把这张饼分成大小相似的两份，现在给定对饼的描述，请你计算分成两块的话，两块重量的差最小是多少（已知所有“节点”重量相同，“边”重量忽略）。

现在sdlwwlp看的眼花缭乱，不得不向你求助，给出节点和边的信息，请您写一个程序帮助傻傻的sdlwwlp分饼。

输入格式

第一行有一个个整数n，m分别表示“节点”个数。

第2..n行（大家不会不知道n个结点树有n-1条边吧？）每行有两个数a，b，表示编号a，b的两个“节点”间有“边”相连。

输出格式

若干行，每行一个数，可以切的边的序号（边的序号即边在输入中的位置，如果有多个最优的解，按序号从小到大输出）。

测试样例1

输入

7

1 2

4 2

3 1

5 2

3 6

7 6

输出

1

3

备注

样例解释：

切断第1条“边”（即1，2之间的边），可以把饼分成[1，3，6，7]和[2，4，5]两部分重量差1

或者是切断第3条，可以分成[3，6，7]和[1，2，4，5]两部分重量差1

数据范围：

对于30%的数据，n<=500;

对于全部数据，n<=40000.

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn = 400000+10;int e,to[maxn],be[maxn],ne[maxn];void add(int x,int y){	to[++e] = y;	ne[e] = be[x];	be[x] = e;}bool p[maxn];int size[maxn],deep[maxn];void dfs(int x){	p[x] = 1;	for(int i = be[x];i;i = ne[i]){		int v = to[i];		if(!p[v]){			deep[v]=deep[x]+1;			dfs(v);			size[x]+=size[v]+1;		}	}}struct T{	int u,v;}a[maxn];struct TT{	int id,z;}tmp[maxn];bool cmp(TT l,TT r){	return l.z==r.z?l.id