“科大讯飞杯”第18届上海大学程序设计联赛(虚树+dp)
发布日期:2021-06-29 12:57:57
浏览次数:3
分类:技术文章
本文共 2691 字,大约阅读时间需要 8 分钟。
参考来自:
G-血压游戏
做法:首先可以发现只有同层的松鼠才会互相打架,也就是说同层的松鼠往上走 如果 相遇 则减一
想到dp:
dp[ u ] 代表的是到了节点 u 为止的最大松鼠数,对于所有子节点 v 来说,如果 dp[ v ] 非零的话,那么 dp[ u ] += max( 1 , dp[ v ] - ( deep[ v ] - deep[ u ] ) ) 就好了,然后根节点特判一下
难点就在于,不能直接在原树上跑这个dp,因为u本身还有一个a[u] 如果加上就会影响下面转移过来的dp
所以现在就将同层的点拿出来建虚树,然后跑dp即可。
说实话,看评论区说 树链剖分+线段树 我也被吓一跳,这么简单的题感觉不用这么复杂吧。然后就等了几天百度博客补题了。
/*学习虚树+lca结构体化+dij*/#includeusing namespace std;typedef long long ll;const ll inf=0x3f3f3f3;const int N=2e5+10;int dfn[N],numdfn;int n,root,max_deep;ll a[N];/* lca部分*/struct LCA{ int head[N],dep[N],fa[N][22],cnt; struct edge { int v,w,next; }e[N*2]; void add(int u,int v,int w) { e[++cnt]={v,w,head[u]};head[u]=cnt; e[++cnt]={u,w,head[v]};head[v]=cnt; } void dfs(int u,int d,int f) { dep[u]=d;fa[u][0]=f; dfn[u]=++numdfn; max_deep=max(max_deep,d); for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(v==f) continue; dfs(v,d+1,u); } } void init() { dfs(root,0,root); for(int k=1;k<=20;++k) for(int i=1;i<=n;++i) fa[i][k]=fa[fa[i][k-1]][k-1]; } int lca(int u,int v) { if(dep[u] =0;--k) if(dep[fa[u][k]]>=dep[v]) u=fa[u][k]; if(u==v) return v; for(int k=20;k>=0;--k) if(fa[u][k]!=fa[v][k]) u=fa[u][k],v=fa[v][k]; return fa[u][0]; }}L;/* 虚树部分*/vector has[N],G[N];int st[N],top,cnt;int numid;bool cmp(int x,int y){ return dfn[x] 1&&dfn[st[top-1]]>=dfn[fa]){ int p1=st[top],p2=st[top-1];//该相邻两节点相连 //建虚树图 G[p1].emplace_back(p2); G[p2].emplace_back(p1); --top; } if(st[top]!=fa){ int p1=st[top],p2=fa; G[p1].emplace_back(p2); G[p2].emplace_back(p1); st[top]=fa; } st[++top]=x;}void build(int id,vector & has){ sort(has.begin(),has.end()); has.erase(unique(has.begin(),has.end()),has.end()); sort(has.begin(),has.end(),cmp); st[top=1]=root; for(int v:has) ins(id,v); //printf("top:%d\n",top); while(top>1) { int p1=st[top],p2=st[top-1]; G[p1].emplace_back(p2); G[p2].emplace_back(p1); --top; }}ll bfs(int u,int fa){ ll ans=0; if(u!=root&&G[u].size()==1) ans=a[u]; for(int v:G[u]){ if(v==fa) continue; ll t=bfs(v,u); if(t) ans+=max(1ll,t-(L.dep[v]-L.dep[u])); } G[u].clear(); return ans;}int main(){ scanf("%d%d",&n,&root); for(int i=1;i<=n;++i) scanf("%lld",&a[i]); for(int i=1;i 1) t--; ans+=t; } if(a[root]>1)a[root]--; ans+=a[root]; printf("%lld\n",ans);}/*4 294 32 72 04 32 43 1*/
转载地址:https://ccsudeer.blog.csdn.net/article/details/105805606 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月05日 06时06分23秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
在图像变换中用最小二乘法求解仿射变换参数
2019-04-29
软件包应用分享|基于RT-Thread的百度语音识别(一)
2019-04-29
12月8日 RCEA - RT-Thread能力认证考试考前通知
2019-04-29
论坛热贴 | RT-Thread音频驱动开发(一)
2019-04-29
基于 Keil MDK 移植 RT-Thread Nano
2019-04-29
【报名截至今晚】12月14日深圳嵌入式与音频开发专题会议预告
2019-04-29
移植 RT-Thread Nano 到 RISC-V
2019-04-29
软件包应用分享|基于RT-Thread的百度语音识别(二)
2019-04-29
在 RT-Thread Nano 上添加控制台与 FinSH
2019-04-29
一站式开发工具:RT-Thread Studio 正式发布
2019-04-29
留言有礼|谢谢你悄悄点了小星星,让我们跃居GitHub RTOS Star榜第一
2019-04-29
功能更新!C 函数也能在 MicroPython 中被调用啦
2019-04-29
东软载波携ES32+RT-Thread走进海尔集团
2019-04-29
今晚8点直播预告:RT-Thread Studio等相关主题答疑
2019-04-29
物联网 20 年简史大揭秘!
2019-04-29
开源项目|RT-Thread 软件包应用作品:水墨屏桌面台历
2019-04-29
珠联璧合!基于i.MX RT和RT-Thread的物联网云接入方案
2019-04-29
基于RTT-MicroPython制作自带BGM的新型肺炎晴雨表
2019-04-29