网站建设合同文百科,青岛最大的设计院,公共资源交易中心网,搜索引擎提交网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一颗树#xff0c;但是这棵树的边是双向的#xff0c;且花费为1。对于每个点#xff0c;可以在连向他的边中选择一条#xff0c;使由这个点到边的另一个点的有向边花费变成1#xff0c;对于每个点都…传送门
文章目录题意思路题意
给你一颗树但是这棵树的边是双向的且花费为1。对于每个点可以在连向他的边中选择一条使由这个点到边的另一个点的有向边花费变成1对于每个点都可以这样选择一条由他出去的有向边使其花费为1要求最小化每两个点之间的最大值。
思路
由于不会证明我的思路以后想明白了再说所以只说一下做法吧。 先找到这棵树直径的中心位置这个可以用dfs找路径的方式轻松找到让后以这个点为根做一棵内向树让每个点的边都连向其父节点那么最大值就是以中心为根的树的最大深度。这个时候并没有结束最后你会发现根节点还没用到考虑什么时候根节点连出去的边能使最大值变小呢如果我们树的最大深度是mxmxmx且有两个子树的最大深度都是这个那么我们不管加到哪里都不会改变最大值。否则的话如果只有一个我们可以将根与这颗子树连一条边这样最大深度就可以减一。让后就是实现的时候注意一下细节就好啦。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,MN*2,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,root;
mapPII,intmp;
vectorintv[N];
int ans[N],d[N];
int e[M],ne[M],h[N],w[M],idx;
int depth[N],res;
bool st[N];
int ed,flag,pre[N];void add(int a,int b,int c)
{e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;
}void dfs_dep(int u,int fa)
{depth[u]depth[fa]1;for(auto x:v[u]){int verx;if(verfa) continue;dfs_dep(ver,u);}
}void dfs(int u,int fa)
{if(flag) return;if(ued) { flag1; return; }for(auto x:v[u]){if(xfa) continue;pre[x]u;dfs(x,u);if(flag) return;pre[x]0;}
}void dfs_add(int u,int fa)
{for(auto x:v[u]){if(xfa) continue;ans[x]mp[{x,u}];dfs_add(x,u);}
}void dfs_d(int u,int fa)
{int mx0;for(auto x:v[u]){if(xfa) continue;dfs_d(x,u);mxmax(mx,depth[x]1);}depth[u]mx;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);memset(h,-1,sizeof(h));scanf(%d,n);for(int i1;in-1;i){int a,b; scanf(%d%d,a,b);v[a].pb(b),v[b].pb(a);mp[{a,b}]i; mp[{b,a}]i;}dfs_dep(1,0);int id0,mx-1;for(int i1;in;i) if(depth[i]mx) mxdepth[i],rooti;memset(depth,0,sizeof(depth));dfs_dep(root,0); mx-1;for(int i1;in;i) if(depth[i]mx) mxdepth[i],edi;dfs(root,0);vectorintv; v.pb(ed);pre[root]0;while(pre[ed]!0) v.pb(pre[ed]),edpre[ed];rootv[v.size()/2];dfs_add(root,0); memset(depth,0,sizeof(depth));dfs_d(root,0);vectorintvv;mx-1;for(int i1;in;i) if(i!root) mxmax(mx,depth[i]);for(int i1;in;i) if(depth[i]mxi!root) vv.pb(i);ans[root]mp[{root,vv[0]}];mx;if(vv.size()1) resmx;else resmx-1;printf(%d\n,res);for(int i1;in;i) printf(%d ,ans[i]);puts();return 0;
}
/**/
