响应式旅行社展业网站开发调研报告,腾讯服务器,怎么做跳转网站 充值登陆,莱芜在线最新消息所谓长链剖分#xff0c;就是对长链进行剖分 #xff08;逃#xff09;
前言
很优雅的算法 利用对指针进行魔法操作将 n2n^2n2 的 dp 优化成线性 线性啊#xff01;#xff01;#xff01;
解析
CF1009F Dominant Indices 给定一棵以 111 为根#xff0c;nnn 个节点… 所谓长链剖分就是对长链进行剖分 逃
前言
很优雅的算法 利用对指针进行魔法操作将 n2n^2n2 的 dp 优化成线性 线性啊
解析
CF1009F Dominant Indices 给定一棵以 111 为根nnn 个节点的树。设 d(u,x)d(u,x)d(u,x) 为 uuu 子树中到 uuu 距离为 xxx 的节点数。 对于每个点求一个最小的 kkk使得 d(u,k)d(u,k)d(u,k) 最大。 长剖板子题 设 fx,df_{x,d}fx,d 表示x子树内到x距离为d的结点个数 则有 fx,d←fson,d−1f_{x,d}\gets f_{son,d-1}fx,d←fson,d−1 所以其实就是下标偏离了一位而已 那么如何解决呢
长链剖分
定义一个子树的深度是子树内深度最大的儿子的深度 定义一个结点的重儿子是子树深度最大的儿子 和重链剖分类似的重儿子连成重链单独结点也算一个重链每个结点都在唯一的重链上
void dfs1(int x,int fa){for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tofa) continue;dfs1(to,x);if(1) son[x]to;}len[x]len[son[x]]1;
}指针偏移
既然我们的父亲dp值只是和儿子相比偏移了一位 那么我们就尝试利用指针的便宜让父亲直接继承儿子的dp 当然继承所有儿子的dp是无法实现的那么我们就让父亲继承重儿子的dp值其他儿子暴力转移
void dp(int x,int fa){f[x][0]1;if(son[x]){f[son[x]]f[x]1;dp(son[x],x);ans[x]ans[son[x]]1;}for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tofa||toson[x]) continue;f[to]now;nowlen[to];dp(to,x);for(int j0;jlen[to];j){f[x][j1]f[to][j];if(f[x][j1]f[x][ans[x]]||(f[x][j1]f[x][ans[x]]j1ans[x])) ans[x]j1;}}if(f[x][ans[x]]1) ans[x]0;
}复杂度证明
每个重链从链头向父亲转移会产生重链长度的代价 由于重链长度和为结点个数所以复杂度为 O(n)O(n)O(n) 注意 和重链剖分不同每个结点到根节点的长链个数可以达到 O(n)O(\sqrt n)O(n) 级别 完整代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N1e6100;
const double eps1e-12;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n;
struct node{int to,nxt;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;return;
}
int son[N],len[N];
int buf[N],*f[N],*nowbuf;
void dfs(int x,int f){for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dfs(to,x);if(len[to]len[son[x]]) son[x]to;}len[x]len[son[x]]1;
}
int ans[N];
void dp(int x,int fa){f[x][0]1;if(son[x]){f[son[x]]f[x]1;dp(son[x],x);ans[x]ans[son[x]]1;}for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tofa||toson[x]) continue;f[to]now;nowlen[to];dp(to,x);for(int j0;jlen[to];j){f[x][j1]f[to][j];if(f[x][j1]f[x][ans[x]]||(f[x][j1]f[x][ans[x]]j1ans[x])) ans[x]j1;}}if(f[x][ans[x]]1) ans[x]0;
}
signed main(){
#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();for(int i1;in;i){int xread(),yread();addline(x,y);addline(y,x);}dfs(1,0);f[1]now;nowlen[1];dp(1,0);for(int i1;in;i) printf(%d\n,ans[i]);return 0;
}
/**/Thanks for reading!
