CF690C3 Brain Network (hard) 题解
2021/11/15 23:10:53
本文主要是介绍CF690C3 Brain Network (hard) 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目大意
一棵树,每次加一个节点,并且询问每次加后的树的直径
解题思路
可以知道,每次加点后最多对树的直径的影响为 \(1\) 。而且有一个重要性质:加进的这个叶子如果能对答案产生贡献,那么这个叶子和原来直径一定有公共端点,所以我们求出每个状态下的 \(u和v和ans\) ,每次要么不更新,要么只更新一个节点。判断是否需要更新需要求 \(lca\) 所以可以先预处理,再加边。
\(code\)
#include <bits/stdc++.h> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } const int maxn=200030; int n,to[maxn],nxt[maxn],head[maxn],num; void add(int x,int y){num++;nxt[num]=head[x];to[num]=y;head[x]=num;} int dep[maxn],fa[maxn],son[maxn],siz[maxn],top[maxn],ans,u,v; void dfs_build(int p,int F) { siz[p]=1; fa[p]=F; dep[p]=dep[F]+1; for(int i=head[p];i;i=nxt[i]) { if(to[i]!=F) { dfs_build(to[i],p); siz[p]+=siz[to[i]]; if(siz[to[i]]>siz[son[p]]) son[p]=to[i]; } } } void dfs_create(int p,int tp) { top[p]=tp; if(son[p])dfs_create(son[p],tp); for(int i=head[p];i;i=nxt[i]) { if(to[i]!=son[p]&&to[i]!=fa[p]) dfs_create(to[i],to[i]); } } int Lca(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); return x; } bool judge(int u,int v) { int l=Lca(u,v); int ss=dep[u]+dep[v]-2*dep[l]; if(ss>ans) {ans=ss;return 1;} return 0; } int main() { n=read(); for(int i=2;i<=n;i++) { fa[i]=read(); add(fa[i],i); } dfs_build(1,1);dfs_create(1,1); u=v=1;ans=0; for(int i=2;i<=n;i++) { int ls=v; if(judge(u,i)) ls=i; if(judge(v,i)) { u=v; ls=i; } v=ls; printf("%d ",ans); } return 0; }
这篇关于CF690C3 Brain Network (hard) 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置