展展示型网站开发,温州网站建设平台,手机商城下载,熊掌号提交wordpress传送门
题意#xff1a;给一棵NNN个结点的树#xff0c;你需要钦定一个根#xff0c;使得所有深度相同的点的度数相同。 N≤100000N \leq 100000N≤100000
用脑子想一想#xff0c;就是根节点直接相连的子树都长得一模一样。
如果根节点度数大于1#xff0c;我们发现它…传送门
题意给一棵NNN个结点的树你需要钦定一个根使得所有深度相同的点的度数相同。
N≤100000N \leq 100000N≤100000
用脑子想一想就是根节点直接相连的子树都长得一模一样。
如果根节点度数大于1我们发现它把整棵树均匀地分成了若干份。所以根节点是重心。
O(N)O(N)O(N)找重心检查一下
如果根节点度数等于1也就是拉了一条链下去
由于是递归的所以走到有岔路的地方就是岔路口所在子树的重心
因为两棵树合并后的重心在原来的重心的路径上所以整棵树的重心在链上。
所以沿一条链走到底就可以了。
但如果有多条路说明重心是岔路口。因为下面长得一模一样所以即使是链长度也都相同。
所以找两条长度不同的链的顶部搜一下即可。
复杂度O(N)O(N)O(N)
#include iostream
#include cstdio
#include cstring
#include cctype
#include algorithm
#define MAXN 100005
#define MAXM 200005
using namespace std;
struct edge{int u,v;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt;
void addnode(int u,int v)
{e[cnt](edge){u,v};nxt[cnt]head[u];head[u]cnt;
}
int siz[MAXN],dep[MAXN],n;
void dfs(int u)
{siz[u]1;for (int ihead[u];i;inxt[i])if (!dep[e[i].v]){dep[e[i].v]dep[u]1;dfs(e[i].v);siz[u]siz[e[i].v];}
}
int maxp[MAXN]{0x7fffffff};
int findroot()
{dfs(dep[1]1);int rt0;for (int u1;un;u){for (int ihead[u];i;inxt[i])if (dep[e[i].v]dep[u]1)maxp[u]max(maxp[u],siz[e[i].v]);if (n-siz[u]maxp[u]) maxp[u]n-siz[u];if (maxp[u]maxp[rt]) rtu;}return rt;
}
int tmp[MAXN];
bool check(int rt)
{memset(siz,0,sizeof(siz));memset(dep,0,sizeof(dep));memset(tmp,0,sizeof(tmp));dep[rt]1;dfs(rt);for (int u1;un;u){int deg0;for (int ihead[u];i;inxt[i])deg;if (!tmp[dep[u]]) tmp[dep[u]]deg;if (tmp[dep[u]]!deg) return false;}return true;
}
int line(int u,int f)
{if (!nxt[head[u]]) return u;if (nxt[nxt[head[u]]]) return 0;int ihead[u];if (e[i].vf) inxt[i];return line(e[i].v,u);
}
int len[MAXN];
inline bool cmp(const int a,const int b){return dep[a]dep[b];}
int main()
{scanf(%d,n);for (int i1;in;i){int u,v;scanf(%d%d,u,v);addnode(u,v);addnode(v,u);}int rtfindroot();if (check(rt)){printf(%d\n,rt);return 0;}for (int ihead[rt];i;inxt[i])len[len[0]]line(e[i].v,rt);sort(len1,lenlen[0]1,cmp);if (len[1]check(len[1])){printf(%d\n,len[1]);return 0;}if (len[len[0]]check(len[len[0]])){printf(%d\n,len[len[0]]);return 0;}puts(-1);return 0;
}
