设计网站vcg,深圳做网站哪个平台好,网站开发的编程软件,水墨风格网站欣赏长链剖分#xff0c;类似于重链剖分(dsu on tree)的一种替代算法。最广泛的用法是优化与深度有关的树上DP#xff0c;以及处理一些与点分治类似的问题。有一部分长链剖分题也可以用dsu on tree做#xff0c;单复杂度往往会多一个log。 每个点找到高度最大的儿子作为自己的重…长链剖分类似于重链剖分(dsu on tree)的一种替代算法。最广泛的用法是优化与深度有关的树上DP以及处理一些与点分治类似的问题。有一部分长链剖分题也可以用dsu on tree做单复杂度往往会多一个log。 每个点找到高度最大的儿子作为自己的重儿子连续的重儿子形成重链。可以发现一个点到根要经过的重链最多为$O(\sqrt{n})$个。一个点的任意祖先所在链长都不小于这个点所在的链长容易证明当重儿子信息$O(1)$传递轻儿子信息$O(轻儿子所在重链长度)$传递时均摊到每个点的复杂度都是$O(1)$总复杂度为$O(n)$。 例一[BZOJ3252]树上“k取方格数”问题选k个叶子使到根路径并权值和最大。 这里只是用到了长链剖分的思想优化。 考虑网络流发现树上不存在退流于是模拟贪心不断找叶子到根的权值最大的路径计入答案后将路径清零。 显然每次可以取一条权值最大的长链即可。 1 #includequeue2 #includecstdio3 #includecstring4 #includeiostream5 #includealgorithm6 #define rep(i,l,r) for (int i(l); i(r); i)7 #define For(i,x) for (int ih[x],k; i; inxt[i])8 typedef long long ll;9 using namespace std;
10
11 const int N200010;
12 ll ans,len[N];
13 int n,k,u,v,cnt,a[N],son[N],h[N],to[N],nxt[N];
14 priority_queuellQ;
15
16 void add(int u,int v){ to[cnt]v; nxt[cnt]h[u]; h[u]cnt; }
17
18 void dfs(int x){
19 For(i,x){
20 dfs(kto[i]);
21 if (len[k]len[son[x]]) son[x]k;
22 }
23 len[x]len[son[x]]a[x];
24 }
25
26 void dfs2(int x,int top){
27 if (xtop) Q.push(len[x]);
28 if (son[x]) dfs2(son[x],top);
29 For(i,x) if ((kto[i])!son[x]) dfs2(k,k);
30 }
31
32 int main(){
33 freopen(bzoj3252.in,r,stdin);
34 freopen(bzoj3252.out,w,stdout);
35 scanf(%d%d,n,k);
36 rep(i,1,n) scanf(%d,a[i]);
37 rep(i,2,n) scanf(%d%d,u,v),add(u,v);
38 dfs(1); dfs2(1,1);
39 while (k !Q.empty()) ansQ.top(),Q.pop(),k--;
40 printf(%lld\n,ans);
41 return 0;
42 } BZOJ3252 例二[CF1009F]对每个子树找到一个深度使该子树内该深度的点最多。 f[x][i]表示x的i级子孙个数发现重儿子的结果可以直接利用轻儿子可以线性合并。 用指针实现二维数组以节省空间。这是此类问题的经典模板。 1 #includecstdio2 #includecstring3 #includeiostream4 #includealgorithm5 #define rep(i,l,r) for (int i(l); i(r); i)6 #define For(i,x) for (int ih[x],k; i; inxt[i])7 typedef long long ll;8 using namespace std;9
10 const int N1000010;
11 int n,u,v,len[N],ans[N],fa[N],son[N],tmp[N],*f[N],*idtmp;
12 int cnt,h[N],nxt[N1],to[N1];
13 void add(int u,int v){ to[cnt]v; nxt[cnt]h[u]; h[u]cnt; }
14
15 void dfs(int x){
16 For(i,x) if ((kto[i])!fa[x]){
17 fa[k]x; dfs(k);
18 if (len[k]len[son[x]]) son[x]k;
19 }
20 len[x]len[son[x]]1;
21 }
22
23 void DP(int x){
24 f[x][0]1;
25 if (son[x]) f[son[x]]f[x]1,DP(son[x]),ans[x]ans[son[x]]1;
26 For(i,x) if ((kto[i])!fa[x] k!son[x]){
27 f[k]id; idlen[k]; DP(k);
28 rep(j,1,len[k]){
29 f[x][j]f[k][j-1];
30 if (f[x][j]f[x][ans[x]] || (f[x][j]f[x][ans[x]] jans[x])) ans[x]j;
31 }
32 }
33 if (f[x][ans[x]]1) ans[x]0;
34 }
35
36 int main(){
37 freopen(1009F.in,r,stdin);
38 freopen(1009F.out,w,stdout);
39 scanf(%d,n);
40 rep(i,2,n) scanf(%d%d,u,v),add(u,v),add(v,u);
41 dfs(1); f[1]id; idlen[1]; DP(1);
42 rep(i,1,n) printf(%d\n,ans[i]);
43 return 0;
44 } CF1009F 例三[COGS2652]树上每个点有两个权值ai,bi找一条长为m的路径使sum(a[i])/sum(b[i])最小。 分数规划后变成找一条长度为m的最小路径同样f[x][i]表示x开始往下的长为i的链的最小权值和为多少。 转移与更新答案显然注意由于重儿子转移过来有一个全部加a[x]的操作于是给每个点记录一个增量就好了。 1 #includecstdio2 #includecstring3 #includeiostream4 #includealgorithm5 #define rep(i,l,r) for (int i(l); i(r); i)6 #define For(i,x) for (int ih[x],k; i; inxt[i])7 typedef long long ll;8 using namespace std;9
10 const int N200010;
11 int n,m,u,v,len[N],fa[N],son[N],a[N],b[N];
12 double val[N],tmp[N],*f[N],*idtmp,ans1e18;
13 int cnt,h[N],nxt[N1],to[N1];
14 void add(int u,int v){ to[cnt]v; nxt[cnt]h[u]; h[u]cnt; }
15
16 void dfs(int x){
17 For(i,x) if ((kto[i])!fa[x]){
18 fa[k]x; dfs(k);
19 if (len[k]len[son[x]]) son[x]k;
20 }
21 len[x]len[son[x]]1;
22 }
23
24 void DP(int x,double mid){
25 val[x]a[x]-mid*b[x]; f[x][0]0;
26 if (son[x]) f[son[x]]f[x]1,DP(son[x],mid),val[x]val[son[x]],f[x][0]-val[son[x]];
27 For(i,x) if ((kto[i])!fa[x] k!son[x]){
28 f[k]id; idlen[k]; DP(k,mid);
29 rep(j,0,min(len[k]-1,m-1))
30 if (m-j-1len[x]) ansmin(ans,f[k][j]val[k]f[x][m-j-1]val[x]);
31 rep(j,0,min(len[k]-1,m-1))
32 f[x][j1]min(f[x][j1],f[k][j]val[k]-val[x]a[x]-mid*b[x]);
33 }
34 if (mlen[x]) ansmin(ans,f[x][m]val[x]);
35 }
36
37 int main(){
38 freopen(cogs2652.in,r,stdin);
39 freopen(cogs2652.out,w,stdout);
40 scanf(%d%d,n,m); m--;
41 rep(i,1,n) scanf(%d,a[i]);
42 rep(i,1,n) scanf(%d,b[i]);
43 rep(i,1,n) ansmin(ans,1.*a[i]/b[i]);
44 if (m-2 || !m){ printf(%.2lf\n,ans); return 0; }
45 rep(i,2,n) scanf(%d%d,u,v),add(u,v),add(v,u);
46 dfs(1); double l0,rN;
47 while (r-l1e-3){
48 double mid(lr)/2;
49 memset(tmp,0x7f,sizeof(tmp)); ans1e18;
50 idtmp; f[1]id; idlen[1]; DP(1,mid);
51 if (ans0) lmid; else rmid;
52 }
53 if (l200000) puts(-1); else printf(%.2lf\n,l);
54 return 0;
55 } COGS2652 例四[BZOJ4543]一棵树中选3个点两两距离相等求方案数。 暴力DP方法加上长链剖分即可。 https://www.cnblogs.com/zhoushuyu/p/9468669.html 1 #includecstdio2 #includecstring3 #includeiostream4 #includealgorithm5 #define rep(i,l,r) for (int i(l); i(r); i)6 #define For(i,x) for (int ih[x],k; i; inxt[i])7 typedef long long ll;8 using namespace std;9
10 const int N100010;
11 ll ans;
12 int n,u,v,len[N],fa[N],son[N],tmp[N2],*f[N],*g[N],*idtmp;
13 int cnt,h[N],nxt[N1],to[N1];
14 void add(int u,int v){ to[cnt]v; nxt[cnt]h[u]; h[u]cnt; }
15
16 void dfs(int x){
17 For(i,x) if ((kto[i])!fa[x]){
18 fa[k]x; dfs(k);
19 if (len[k]len[son[x]]) son[x]k;
20 }
21 len[x]len[son[x]]1;
22 }
23
24 void DP(int x){
25 if (son[x]) f[son[x]]f[x]1,g[son[x]]g[x]-1,DP(son[x]);
26 f[x][0]1; ansg[x][0];
27 For(i,x) if ((kto[i])!fa[x] k!son[x]){
28 f[k]id; idlen[k]1; g[k]id; idlen[k]1; DP(k);
29 rep(j,0,len[k]-1){
30 if (j) ansf[x][j-1]*g[k][j];
31 ansg[x][j1]*f[k][j];
32 }
33 rep(j,0,len[k]-1){
34 g[x][j1]f[x][j1]*f[k][j];
35 if (j) g[x][j-1]g[k][j];
36 f[x][j1]f[k][j];
37 }
38 }
39 }
40
41 int main(){
42 freopen(bzoj4543.in,r,stdin);
43 freopen(bzoj4543.out,w,stdout);
44 scanf(%d,n);
45 rep(i,2,n) scanf(%d%d,u,v),add(u,v),add(v,u);
46 dfs(1); f[1]id; idlen[1]1; g[1]id; idlen[1]1;
47 DP(1); printf(%lld\n,ans);
48 return 0;
49 } BZOJ4543 例五[BZOJ3653]谈笑风生 同样没有什么要说的暴力统计以深度为下标的信息用上长链剖分复杂度就有保证了。 注意我们长链剖分的时候无法记录前缀和但可以记录后缀和且后缀和也是可以DP直接转移的。 1 #includecstdio2 #includevector3 #includecstring4 #includeiostream5 #includealgorithm6 #define rep(i,l,r) for (int i(l); i(r); i)7 #define For(i,x) for (int ih[x],k; i; inxt[i])8 typedef long long ll;9 using namespace std;
10
11 const int N300010;
12 int n,u,v,Q,dep[N],fa[N],son[N];
13 int cnt,len[N],sz[N],h[N],nxt[N1],to[N1];
14 ll ans[N],tmp[N],*f[N],*idtmp;
15 struct P{ int x,y; };
16 vectorPve[N];
17 void add(int u,int v){ to[cnt]v; nxt[cnt]h[u]; h[u]cnt; }
18
19 void dfs(int x){
20 dep[x]dep[fa[x]]1; sz[x]1;
21 For(i,x) if ((kto[i])!fa[x]){
22 fa[k]x; dfs(k); sz[x]sz[k];
23 if (len[k]len[son[x]]) son[x]k;
24 }
25 len[x]len[son[x]]1;
26 }
27
28 void DP(int x){
29 if (son[x]) f[son[x]]f[x]1,DP(son[x]),f[x][0]f[son[x]][0];
30 f[x][0]sz[x]-1;
31 For(i,x) if ((kto[i])!fa[x] k!son[x]){
32 f[k]id; idlen[k]; DP(k);
33 rep(j,0,len[k]-1) f[x][j1]f[k][j];
34 f[x][0]f[k][0];
35 }
36 int edve[x].size()-1;
37 rep(i,0,ed){
38 int kve[x][i].y,idve[x][i].x;
39 ans[id]1ll*(sz[x]-1)*min(dep[x]-1,k);
40 if (klen[x]-1) ans[id]f[x][0]-sz[x]1;
41 else ans[id]f[x][0]-sz[x]1-f[x][k1];
42 }
43 }
44
45 int main(){
46 freopen(bzoj3653.in,r,stdin);
47 freopen(bzoj3653.out,w,stdout);
48 scanf(%d%d,n,Q);
49 rep(i,2,n) scanf(%d%d,u,v),add(u,v),add(v,u);
50 dfs(1);
51 rep(i,1,Q) scanf(%d%d,u,v),ve[u].push_back((P){i,v});
52 f[1]id; idlen[1]; DP(1);
53 rep(i,1,Q) printf(%lld\n,ans[i]);
54 return 0;
55 } BZOJ3653 转载于:https://www.cnblogs.com/HocRiser/p/10416144.html
