CF860E Arkady and a Nobody-men
2024-09-02 22:00:56
CF860E Arkady and a Nobody-men
类比LNOI2014 LCA那个题,其实树剖可以过。。。。(用树状数组区间加区间求和更快!)
巧妙的nlogn做法是:
(其实第二个式子有锅,应当再加上dep[fa[x]])
对于同一层的考虑处理lca问题
一定要排个序处理
dfs是处理树上顺序的有力武器!
按dfs从小到大,一个x的前面的所有点的lca深度单调不降
可以用一个单调栈维护,只用维护:最后的位置(宽度),深度(键值),代表的点
如果和栈顶的代表点的lca深度比栈顶的键值小,那么pop栈顶,等价于把些点合并!
详见代码:
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
#define pb push_back
#define solid const auto &
#define enter cout<<endl
#define pii pair<int,int>
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);(fl==true)&&(x=-x);}
template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}
template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
namespace Modulo{
const int mod=;
int ad(int x,int y){return (x+y)>=mod?x+y-mod:x+y;}
void inc(int &x,int y){x=ad(x,y);}
int mul(int x,int y){return (ll)x*y%mod;}
void inc2(int &x,int y){x=mul(x,y);}
int qm(int x,int y=mod-){int ret=;while(y){if(y&) ret=mul(x,ret);x=mul(x,x);y>>=;}return ret;}
}
//using namespace Modulo;
namespace Miracle{
const int N=5e5+;
int n;
int fa[N][];
ll g[N];
struct node{
int nxt,to;
}e[N];
int hd[N],cnt;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
int dfn[N],df;
int dep[N];
vector<int>mem[N];
int mx;
void dfs(int x,int d){
dep[x]=d;
mx=max(mx,d);
mem[d].pb(x);
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
dfs(y,d+);
}
}
struct po{
int id,pos,d;
po(){}
po(int ii,int dd,int pp){
id=ii;pos=pp;d=dd;
}
}sta[N];
int top;
ll calc(){
if(!top) return ;
return (ll)(sta[top].pos-sta[top-].pos)*sta[top].d;
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(reg j=;j>=;--j){
if(dep[fa[x][j]]>=dep[y]) x=fa[x][j];
}
if(x==y) return x;
for(reg j=;j>=;--j){
if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
}
return fa[x][];
}
void sol(vector<int>&v){
int o=;
top=;
ll val=;
for(solid x:v){
if(!o){
++top;sta[top]=po(x,,);
}
else{
while(){
int y=lca(sta[top].id,x);
if(dep[y]>=sta[top].d){
++top;sta[top]=po(x,dep[y],o);break;
}
val-=calc();
--top;
}
val+=calc();
g[x]+=val;
}
++o;
}
}
int main(){
rd(n);
int rt=;
for(reg i=;i<=n;++i){
rd(fa[i][]);if(fa[i][]==) rt=i;
else add(fa[i][],i);
}
dfs(rt,);
for(reg j=;j<=;++j){
for(reg i=;i<=n;++i){
fa[i][j]=fa[fa[i][j-]][j-];
}
}
for(reg i=;i<=mx;++i){
for(solid x:mem[i]) g[x]=g[fa[x][]]+i-;
sol(mem[i]);
reverse(mem[i].begin(),mem[i].end());
sol(mem[i]);
}
prt(g,,n);
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
*/
LCA和dfs本身着关系,
这里利用的本质上是,两个点的lca就是dfs栈不断回溯后,第一次前进下来的点就是lca(分叉地方)
O(1)LCA也是利用这个性质
最新文章
- Windows Server 2008 下解析二级域名的方法
- Django1.3 创建项目
- MySQL for Windows 解压缩版安装 和 多实例安装
- iOS 简单动画 序列帧动画
- 20145212《Java程序设计》实验报告一:Java开发环境的熟悉(Windows+IDE)
- QT_BEGIN_NAMESPACE QT_END_NAMESPACE
- JSON.stringify初识
- java使用JDBC连接数据库
- JavaScript之延迟加载
- FZU 2233 ~APTX4869 贪心+并查集
- [BZOJ 1066] [SCOI2007] 蜥蜴 【最大流】
- Unable to resolve target &#39;android-14&#39; 解决办法
- 凡客副总裁崔晓琦离职 曾负责旗下V+商城项目_科技_腾讯网
- MvcOptions配置
- 官方windows10升级工具
- Vue过渡效果之CSS过渡
- Spring 对缓存的抽象
- 输入和输出--java序列化机制
- MyBatis学习---整合SpringMVC
- c++ 重点随记