水贝网站建设,手机上怎么制作app软件,昆明网约车公司排行榜,开发网站用什么语言好正题
nowcoder 20107-C 题目大意
给一棵树#xff0c;让你构造一个序列a#xff0c;使得a中的数互不相等#xff0c;且相邻点是祖先的关系#xff0c;回答序列最长长度 解题思路
书中的每个点可以把字数的两个序列连起来
考虑维护一个堆#xff0c;存子树中的序列让你构造一个序列a使得a中的数互不相等且相邻点是祖先的关系回答序列最长长度 解题思路
书中的每个点可以把字数的两个序列连起来
考虑维护一个堆存子树中的序列每次从子树中找两个最大的序列然后合并起来其他的上传到当前堆这里合并堆可以用启发式合并 code
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define N 100100
#define ll long long
using namespace std;
int T,n,x,y,tot,h[N],hs[N],sz[N],to[N];
priority_queueintd[N];
struct rec
{int to,nx;
}e[N1];
void add(int x,int y)
{e[tot].toy;e[tot].nxh[x];h[x]tot;return;
}
void dfs(int x,int fa)
{hs[x]0;sz[x]1;for(int ih[x];i;ie[i].nx){int ye[i].to;if(yfa)continue;dfs(y,x);sz[x]sz[y];if(sz[y]sz[hs[x]])hs[x]y;}if(hs[x])to[x]to[hs[x]];for(int ih[x];i;ie[i].nx){int ye[i].to;if(yfa||yhs[x])continue;while(!d[to[y]].empty())d[to[x]].push(d[to[y]].top()),d[to[y]].pop();//上传}if(d[to[x]].size()2){int g1d[to[x]].top();//找最大的两个d[to[x]].pop();int g2d[to[x]].top();d[to[x]].pop();d[to[x]].push(g1g21);}else if(d[to[x]].size()1){int g1d[to[x]].top();d[to[x]].pop();d[to[x]].push(g11);}else d[to[x]].push(1);return;
}
int main()
{scanf(%d,T);while(T--){scanf(%d,n);for(int i1;in;i)to[i]i;tot0;memset(h,0,sizeof(h));for(int i1;in;i){scanf(%d%d,x,y);add(x,y);add(y,x);}dfs(1,0);printf(%d\n,d[to[1]].top());for(int i1;in;i)while(!d[to[i]].empty())d[to[i]].pop();}return 0;
}
