1024问

牛客 - 王国(虚树+树的直径)

Kenda ·
更新时间:2024-09-21
· 738 次阅读

题目链接：点击查看

题目大意：给出 n 个点组成的一棵树，每个节点都有一个权值，现在规定权值相同的节点之间，简单路径的边数为 x ，求 x * x 的最大值

题目分析：真的很巧，上周刚学的虚树，读完这个题的第一反应就是可以用虚树简化题目，其实完全可以用树形dp跑一遍dfs出来，可奈何我dp不好，就只能用虚树来做了

题目中有两个点可以单独考虑，首先是权值相同的点，这个就可以用虚树将权值相同的点都拎出来，然后是简单路径的边数最大，这个对应着树的直径，所以直接虚树配合树的直径写一个dfs，直接维护最大值就好了

代码：
 

#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const int N=1e5+100; vectorpos[N]; bool cmp(int x,int y); struct virtual_tree { //原树部分 struct { int to,next; }edge[N<<1]; int head[N],cnt,deep[N],dp[N][20],limit;//树上倍增 int L[N],R[N],dfn;//dfs序 void addedge(int u,int v) { edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u,int fa,int dep) { L[u]=++dfn; deep[u]=dep; dp[u][0]=fa; for(int i=1;i<=limit;i++) dp[u][i]=dp[dp[u][i-1]][i-1]; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v!=fa) dfs(v,u,dep+1); } R[u]=dfn; } int LCA(int x,int y) { if(deep[x]=0;i--) if(deep[x]-deep[y]>=(1<=0;i--) if(dp[x][i]!=dp[y][i]) { x=dp[x][i]; y=dp[y][i]; } return dp[x][0]; } void init(int n) { memset(head,-1,sizeof(head)); cnt=dfn=0; limit=log2(n)+1; for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } } //虚树部分 vectornode[N]; vectorver; int Stack[N]; void build() { sort(ver.begin(),ver.end(),cmp); int sz=ver.size()-1; for(int i=0;i<sz;i++) ver.push_back(LCA(ver[i],ver[i+1])); sort(ver.begin(),ver.end(),cmp); ver.erase(unique(ver.begin(),ver.end()),ver.end()); int top=0; Stack[++top]=ver[0]; for(int i=1;i<ver.size();i++) { while(top&&R[Stack[top]]<L[ver[i]]) top--; if(top) node[Stack[top]].push_back(ver[i]); Stack[++top]=ver[i]; } } void clear() { for(int i=0;i<ver.size();i++) node[ver[i]].clear(); ver.clear(); } int d[N],ans; void dfs(int u,int fa) { d[u]=0; for(auto v:node[u]) { if(v==fa) continue; dfs(v,u); int w=deep[v]-deep[u]; ans=max(ans,d[v]+d[u]+w); d[u]=max(d[u],d[v]+w); } } LL solve(int val) { ver=pos[val]; build();//建虚树 ans=0; dfs(ver.front(),-1);//树形dp求树的直径 clear();//初始化 return ans; } }tree; bool cmp(int x,int y) { return tree.L[x]<tree.L[y]; } int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false); int n; scanf("%d",&n); for(int i=1;i<=n;i++) { int num; scanf("%d",&num); pos[num].push_back(i); } tree.init(n); tree.dfs(1,0,0); LL mmax=0; for(int i=1;i<=n;i++) if(pos[i].size()) mmax=max(mmax,tree.solve(i)); printf("%lld\n",mmax*mmax); return 0; } Frozen_Guardian 原创文章 741获赞 43访问量 5万+ 关注 私信 展开阅读全文
作者：Frozen_Guardian



牛客

1024 个赞
编辑 举报
需要 登录 后方可回复, 如果你还没有账号请 注册新账号
相关文章
三个很特别的CSS小技巧分享
Orianna 2021-07-12
838
【牛客】左右最值最大差
Gelsey 2020-11-09
602
牛客网+华为云+宝塔面板 服务器小白保姆级配置
Elina 2020-07-01
871
【牛客】另类加法
Tama 2020-09-20
557
牛客小白月赛23
Nona 2021-07-24
896
牛客小白月赛23 A-膜法记录（贪心+枚举）
Sahar 2021-06-03
669
牛客 - 奇怪的背包问题增加了(贪心)
Victoria 2021-01-04
790
【牛客】微信红包
Heather 2021-03-08
764
牛客算法周周练1
Haile 2020-10-22
703
牛客练习赛61 - A - 打怪
Gita 2020-01-30
579
牛客网数据库SQL 实战答案解析
Tricia 2021-04-30
712
牛客算法周周练全部题解
Phemia 2020-02-20
788
牛客算法周周练3
Serepta 2020-01-01
819
[ACM]【树形DP】牛客练习赛62 牛牛染颜色
Iona 2020-07-28
600
牛客练习赛62(基于官方题解的补题 A ~ D)
Cerelia 2021-07-02
783
牛客 - 王国(虚树+树的直径)
Kenda 2021-04-05
738
左神算法、牛客网算法-初级2-3（python实现）
Gloria 2020-09-22
987
D 景区路线规划 （期望 DP 牛客算法周周练1）
Talia 2020-04-13
696
【牛客小白月赛23 A】膜法记录 （二进制枚举）
Antonia 2020-11-03
966
牛客练习赛63-B牛牛的鱼缸
Yelena 2021-03-20
752