常德做网站公司,帮做网站制作挣钱,那个网站做的好,logo设计图片免费 图案正题
题目链接:https://ac.nowcoder.com/acm/contest/20107/C 题目大意
给出nnn个点的一棵树#xff0c;求一个最长的序列使得数字互不相同且相邻编号节点的都是祖孙关系。 1≤n≤105,1≤T≤51\leq n\leq 10^5,1\leq T\leq 51≤n≤105,1≤T≤5 解题思路 wx,iw_{x,i}wx,i表…正题
题目链接:https://ac.nowcoder.com/acm/contest/20107/C 题目大意
给出nnn个点的一棵树求一个最长的序列使得数字互不相同且相邻编号节点的都是祖孙关系。
1≤n≤105,1≤T≤51\leq n\leq 10^5,1\leq T\leq 51≤n≤105,1≤T≤5 解题思路
wx,iw_{x,i}wx,i表示节点xxx第iii次下来最多能获得的代价保证前面最优的情况那么转移的时候我们之间把子节点的www从大到小排序然后因为节点xxx有一次额外机会向下所以我们还要把前两个最大的www给合并。
这个过程用启发式合并堆就好了时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N1e510;
struct node{int to,next;
}a[N1];
int T,n,tot,ls[N],siz[N],son[N];
priority_queueint s[N],q;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa){siz[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}return;
}
void solve(int x,int fa,int top){for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||yson[x])continue;solve(y,x,y);}if(son[x])solve(son[x],x,top);for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||yson[x])continue;while(!s[y].empty())q.push(s[y].top()),s[y].pop();}int w0;if(!q.empty())wq.top(),q.pop();if(!q.empty())wq.top(),q.pop();q.push(w1);if(xtop)while(!q.empty())s[x].push(q.top()),q.pop();return;
}
int main()
{scanf(%d,T);while(T--){memset(ls,0,sizeof(ls));memset(son,0,sizeof(son));scanf(%d,n);tot0;for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}dfs(1,1);solve(1,1,1);printf(%d\n,s[1].top());while(!s[1].empty())s[1].pop();}return 0;
}
