ツリーチェーン分割チュートリアル&bzoj 1036[ZJOI 2008]ツリーの統計Count問題解
転載は以下のことを明記してください.http://blog.csdn.net/jiangshibiao/article/details/24669751
【原題】
1036:[ZJOI 2008]ツリーの統計Count
Time Limit: 10 Sec
Memory Limit: 162 MB
Submit: 4465
Solved: 1858
[ Submit][ Status]
Description
1本の木にはn個のノードがあり、番号はそれぞれ1からnであり、各ノードには重みwがある.私たちは以下の形式であなたにこの木に対していくつかの操作を完成するように要求します:I.CHANGE u t:ノードuの重み値をt IIに変更します.QMAX u v:点uから点vへの経路上のノードの最大重みIII.QSUM u v:点uから点vへの経路上のノードの重み値と注意を尋ねる:点uから点vへの経路上のノードはuとvそのものを含む
Input
入力された第1の動作は、ノードの個数を表す整数nである.次にn−1行、各行2個の整数aおよびbは、ノードaとノードbとの間にエッジが接続されていることを示す.次にn行、各行に1つの整数、i行目の整数wiはノードiの重み値を表す.次の1行は、操作の総数を表す整数qである.次にq行は、各行に1つの動作を「CHANGE u t」または「QMAXu v」または「QSUM u v」の形式で与える.100%のデータに対して、1<=n<=30000、0<=q<=20000を保証する.途中操作では、各ノードの重みwが−30000〜30000の間であることが保証される.
Output
各「QMAX」または「QSUM」の動作について、各行に出力される整数は、出力を要求する結果を表す.
Sample Input
4 1 2 2 3 4 1 4 2 1 3 12 QMAX 3 4 QMAX 3 3 QMAX 3 2 QMAX 2 3 QSUM 3 4 QSUM 2 1 CHANGE 1 5 QMAX 3 4 CHANGE 3 6 QMAX 3 4 QMAX 2 4 QSUM 3 4
Sample Output
4 1 2 2 10 6 5 6 5 16
HINT
Source
木の分治
【序言】私は木の鎖で分割した==木の分治は書くのがもっと面倒です.私は今日入門したばかりです==で、問題解を書いて印象を深めました.
頭の中に残っている勉強していない前の考えがあるので、このチュートリアルは初心者に向いているのではないでしょうか.各道の大牛ももっと指導してほしい.
以下の内容は1篇の言う悪くない教程を結びつけて、私はいくつかの変更を加えて、もっと分かりやすいでしょう.オリジナル大牛も釈然としません==.
【問題】1本の木で経路の修正、極値の求め、和の求めを行う.
【木の鎖の断分の概念】木の鎖は、木の上の経路です.分割とは,経路を重鎖と軽鎖に分類することである.ツリーチェーン分割とは、いくつかの点をパスに合成し、セグメントツリーの番号(下付き)を秩序化させ、セグメントツリーで維持することで、クエリー、修正の効率が大幅に向上します(ブロック思想に似ています).経路をチェーンに分けて(どのように分けているかは気にしないで)、2つのポイントペア(x,y)を尋ねるたびに、xとyが同じチェーンにある場合、線分ツリーのuとv(同じチェーンに下付きが連続しているため)u、vはx、yに対応する線分ツリーのポイントを直接尋ねるとします.そうでなければ、深さの大きい点から少しずつ登って、その点があるチェーンの状況をx,yが同じチェーンになるまで記録します.
【注意】ツリーチェーン分割におけるセグメントツリーにおける各点が表す意味は、原図のエッジまたは点であってもよい.この問題は点だから,私は点で述べる.
【配列の意味の概要】num[v]はvをルートとするサブツリーのノード数を表し、deep[v]はvの深さ(ルートの深さが1)を表し、top[v]はvが存在するチェーンの先端ノードを表し、f[v]はvの父親を表し、son[v]はvと同じ重鎖上のvの息子ノード(一応重息子と呼ぶ)、tree[v]はセグメントツリーにおけるノードvの番号を表し、pre[v]は、セグメントツリーの番号がvのノードに対応する原図の点(treeとは反対)を表す
これらのものを求めるだけで、lognの時間で元の問題の操作を完了することができます.
【用語解釈】重子:num[u]がvのサブノードのnum値が最も大きい場合、uはvの重子である.軽息子:vの他のサブノード.重辺:点vとその重さの息子の縁.軽辺:点vと軽息子の連辺.重鎖:重辺で連結されたパス.軽量チェーン:軽量エッジ.分割後のツリーには、(v,u)が軽辺であればsiz[u]*2証明については、私は証明しません~~(実は私はできません)応用して、複雑さを知っていればいいです.
【前処理アルゴリズム実装】fa、deep、num、son、top、tree、preを2つのdfsで求めることができる. dfs_1:fa、deep、num、sonを求めるのは簡単です. dfs_2:1 tree[v](検索順)を順次マークしながらpreを得る.
②vについて、son[v]が存在する(すなわち、vがリーフノードではない)場合、明らかにtop[son[v]=top[v]がある.(なしで終了)
③それから、まずvの重息子uを検索し、uの重息子、重孫を...のtop値もtop[v]に設定します.
④次にvの軽息子uを検索し、uの重息子、重孫を...のtop値をuに設定します.
ツリー内の各エッジの重み値をセグメントツリーで更新すると、チェーン作成とセグメントツリー作成のプロセスが完了します.
【クエリー&修正アルゴリズム実装】
例えば、uからvへの経路上の各エッジの重み値にxを加算する.f 1=top[u]、f 2=top[v]と記す.f 1<>f 2の場合、dep[f 1]>=dep[f 2]を設定すると、uからf 1の重み値(logn)が更新され、u=f[f 1]となる.f 1=f 2の場合:uとvは同じ重鎖上にあり、uからv経路上の点の重み値(logn)を直接更新し、修正が完了する.修正が完了するまで、上記の手順を繰り返します.
下図に示すように、太いのは重辺、細いのは軽辺です.(軽辺は実質的に長さ1のチェーン)ノード番号の横に赤い点があり、そのノードがチェーンの先端ノードであることを示しています.青い数字は無視してください=(copy人家図なので、彼のセグメントツリーにはエッジが保存されています)![树链剖分教程 & bzoj 1036 [ZJOI2008] 树的统计 Count 题解_第1张图片](https://s1.md5.ltd/image/28dc5841175ae8188f7dbf6c4aaf4966.jpg)
11から10のパスを変更すると仮定します.私たちは11と10の絶え間ない登り(具体的な操作は上を参照)を通じて、彼らを最終的に1番の点で交差させます.このように,11は重鎖2−−11のみ,10は自己と鎖1−14のみを通過し,かなり効率が高い.(なんでACオートマトンに似てるんだろう)
【原題に戻る】これで、原題は裸の木の鎖が切れた.具体的な注釈はコードを参照してください.
【コード】
【原題】
1036:[ZJOI 2008]ツリーの統計Count
Time Limit: 10 Sec
Memory Limit: 162 MB
Submit: 4465
Solved: 1858
[ Submit][ Status]
Description
1本の木にはn個のノードがあり、番号はそれぞれ1からnであり、各ノードには重みwがある.私たちは以下の形式であなたにこの木に対していくつかの操作を完成するように要求します:I.CHANGE u t:ノードuの重み値をt IIに変更します.QMAX u v:点uから点vへの経路上のノードの最大重みIII.QSUM u v:点uから点vへの経路上のノードの重み値と注意を尋ねる:点uから点vへの経路上のノードはuとvそのものを含む
Input
入力された第1の動作は、ノードの個数を表す整数nである.次にn−1行、各行2個の整数aおよびbは、ノードaとノードbとの間にエッジが接続されていることを示す.次にn行、各行に1つの整数、i行目の整数wiはノードiの重み値を表す.次の1行は、操作の総数を表す整数qである.次にq行は、各行に1つの動作を「CHANGE u t」または「QMAXu v」または「QSUM u v」の形式で与える.100%のデータに対して、1<=n<=30000、0<=q<=20000を保証する.途中操作では、各ノードの重みwが−30000〜30000の間であることが保証される.
Output
各「QMAX」または「QSUM」の動作について、各行に出力される整数は、出力を要求する結果を表す.
Sample Input
4 1 2 2 3 4 1 4 2 1 3 12 QMAX 3 4 QMAX 3 3 QMAX 3 2 QMAX 2 3 QSUM 3 4 QSUM 2 1 CHANGE 1 5 QMAX 3 4 CHANGE 3 6 QMAX 3 4 QMAX 2 4 QSUM 3 4
Sample Output
4 1 2 2 10 6 5 6 5 16
HINT
Source
木の分治
【序言】私は木の鎖で分割した==木の分治は書くのがもっと面倒です.私は今日入門したばかりです==で、問題解を書いて印象を深めました.
頭の中に残っている勉強していない前の考えがあるので、このチュートリアルは初心者に向いているのではないでしょうか.各道の大牛ももっと指導してほしい.
以下の内容は1篇の言う悪くない教程を結びつけて、私はいくつかの変更を加えて、もっと分かりやすいでしょう.オリジナル大牛も釈然としません==.
【問題】1本の木で経路の修正、極値の求め、和の求めを行う.
【木の鎖の断分の概念】木の鎖は、木の上の経路です.分割とは,経路を重鎖と軽鎖に分類することである.ツリーチェーン分割とは、いくつかの点をパスに合成し、セグメントツリーの番号(下付き)を秩序化させ、セグメントツリーで維持することで、クエリー、修正の効率が大幅に向上します(ブロック思想に似ています).経路をチェーンに分けて(どのように分けているかは気にしないで)、2つのポイントペア(x,y)を尋ねるたびに、xとyが同じチェーンにある場合、線分ツリーのuとv(同じチェーンに下付きが連続しているため)u、vはx、yに対応する線分ツリーのポイントを直接尋ねるとします.そうでなければ、深さの大きい点から少しずつ登って、その点があるチェーンの状況をx,yが同じチェーンになるまで記録します.
【注意】ツリーチェーン分割におけるセグメントツリーにおける各点が表す意味は、原図のエッジまたは点であってもよい.この問題は点だから,私は点で述べる.
【配列の意味の概要】num[v]はvをルートとするサブツリーのノード数を表し、deep[v]はvの深さ(ルートの深さが1)を表し、top[v]はvが存在するチェーンの先端ノードを表し、f[v]はvの父親を表し、son[v]はvと同じ重鎖上のvの息子ノード(一応重息子と呼ぶ)、tree[v]はセグメントツリーにおけるノードvの番号を表し、pre[v]は、セグメントツリーの番号がvのノードに対応する原図の点(treeとは反対)を表す
これらのものを求めるだけで、lognの時間で元の問題の操作を完了することができます.
【用語解釈】重子:num[u]がvのサブノードのnum値が最も大きい場合、uはvの重子である.軽息子:vの他のサブノード.重辺:点vとその重さの息子の縁.軽辺:点vと軽息子の連辺.重鎖:重辺で連結されたパス.軽量チェーン:軽量エッジ.分割後のツリーには、(v,u)が軽辺であればsiz[u]*2
【前処理アルゴリズム実装】fa、deep、num、son、top、tree、preを2つのdfsで求めることができる. dfs_1:fa、deep、num、sonを求めるのは簡単です. dfs_2:1 tree[v](検索順)を順次マークしながらpreを得る.
②vについて、son[v]が存在する(すなわち、vがリーフノードではない)場合、明らかにtop[son[v]=top[v]がある.(なしで終了)
③それから、まずvの重息子uを検索し、uの重息子、重孫を...のtop値もtop[v]に設定します.
④次にvの軽息子uを検索し、uの重息子、重孫を...のtop値をuに設定します.
ツリー内の各エッジの重み値をセグメントツリーで更新すると、チェーン作成とセグメントツリー作成のプロセスが完了します.
【クエリー&修正アルゴリズム実装】
例えば、uからvへの経路上の各エッジの重み値にxを加算する.f 1=top[u]、f 2=top[v]と記す.f 1<>f 2の場合、dep[f 1]>=dep[f 2]を設定すると、uからf 1の重み値(logn)が更新され、u=f[f 1]となる.f 1=f 2の場合:uとvは同じ重鎖上にあり、uからv経路上の点の重み値(logn)を直接更新し、修正が完了する.修正が完了するまで、上記の手順を繰り返します.
下図に示すように、太いのは重辺、細いのは軽辺です.(軽辺は実質的に長さ1のチェーン)ノード番号の横に赤い点があり、そのノードがチェーンの先端ノードであることを示しています.青い数字は無視してください=(copy人家図なので、彼のセグメントツリーにはエッジが保存されています)
![树链剖分教程 & bzoj 1036 [ZJOI2008] 树的统计 Count 题解_第1张图片](https://img.md5.com/image/info5/e43e9f95548140e2b1c54935b5370ffc.jpg)
11から10のパスを変更すると仮定します.私たちは11と10の絶え間ない登り(具体的な操作は上を参照)を通じて、彼らを最終的に1番の点で交差させます.このように,11は重鎖2−−11のみ,10は自己と鎖1−14のみを通過し,かなり効率が高い.(なんでACオートマトンに似てるんだろう)【原題に戻る】これで、原題は裸の木の鎖が切れた.具体的な注釈はコードを参照してください.
【コード】
#include<cstdio>
#define S [30005]
#define T [120005]
#define SS [60005]
using namespace std;
struct arr{int l,r,sum,max;}a T; //
struct adj{int next,go;}adj SS; //
int tree S,pre S,end S,son S,f S,data S,num S,top S,deep S;
int n,i,x,y,cnt,tot,Q;
char opt[10];
int Max(int a,int b){return (a>b)?a:b;}
void add(int u,int v){adj[++cnt].go=v;adj[cnt].next=end[u];end[u]=cnt;}
void dfs1(int k,int fa,int d) //
{
deep[k]=d;f[k]=fa;num[k]=1;
for (int i=end[k];i;i=adj[i].next)
{
int go=adj[i].go;if (go==fa) continue;
dfs1(go,k,d+1);num[k]+=num[go];
if (!son[k]||num[go]>num[son[k]]) son[k]=go;
}
}
void dfs2(int k,int Number)
{
top[k]=Number;tree[k]=++tot; //tree[i] i
pre[tree[k]]=k; //pre[i] i
if (!son[k]) return;
dfs2(son[k],Number); // ， “ ” Number
for (int i=end[k];i;i=adj[i].next)
{
int go=adj[i].go;
if (go!=son[k]&&go!=f[k]) dfs2(go,go); //
}
}
void build(int k,int l,int r) //
{
a[k].l=l;a[k].r=r;
if (l==r) {a[k].sum=a[k].max=data[pre[l]];return;}
int mid=(l+r)>>1;
build(k<<1,l,mid);build((k<<1)+1,mid+1,r);
a[k].sum=a[k<<1].sum+a[(k<<1)+1].sum;
a[k].max=Max(a[k<<1].max,a[(k<<1)+1].max);
}
void update(int k,int x,int jia)//
{
if (a[k].l==a[k].r)
{
a[k].sum+=jia*(a[k].r-a[k].l+1);
a[k].max+=jia;return;
}
int mid=(a[k].l+a[k].r)>>1;
if (x<=mid) update(k<<1,x,jia);else update((k<<1)+1,x,jia);
a[k].sum=a[k<<1].sum+a[(k<<1)+1].sum;
a[k].max=Max(a[k<<1].max,a[(k<<1)+1].max);
}
int ask_sum(int k,int x,int y)//
{
if (a[k].l>=x&&a[k].r<=y) return a[k].sum;
int mid=(a[k].l+a[k].r)>>1,o=0;
if (x<=mid) o+=ask_sum(k<<1,x,y);
if (y>mid) o+=ask_sum((k<<1)+1,x,y);
a[k].sum=a[k<<1].sum+a[(k<<1)+1].sum;
a[k].max=Max(a[k<<1].max,a[(k<<1)+1].max);
return o;
}
int ask_max(int k,int x,int y)// ，
{
if (a[k].l>=x&&a[k].r<=y) return a[k].max;
int mid=(a[k].l+a[k].r)>>1,o=-1000000000;
if (x<=mid) o=ask_max(k<<1,x,y);
if (y>mid) o=Max(o,ask_max((k<<1)+1,x,y));
a[k].sum=a[k<<1].sum+a[(k<<1)+1].sum;
a[k].max=Max(a[k<<1].max,a[(k<<1)+1].max);
return o;
}
int find_max(int x,int y)
{
int f1=top[x],f2=top[y],t,ans=-1000000000;// ans -INF
while (f1!=f2)
{
if (deep[f1]<deep[f2]) t=f1,f1=f2,f2=t,t=x,x=y,y=t;
ans=Max(ans,ask_max(1,tree[f1],tree[x]));
x=f[f1];f1=top[x];
}
ans=Max(ans,(deep[x]>deep[y])?ask_max(1,tree[y],tree[x]):ask_max(1,tree[x],tree[y]));
return ans;
}
int find_sum(int x,int y)
{
int f1=top[x],f2=top[y],t,ans=0;
while (f1!=f2)
{
if (deep[f1]<deep[f2]) t=f1,f1=f2,f2=t,t=x,x=y,y=t;
ans+=ask_sum(1,tree[f1],tree[x]);
x=f[f1];f1=top[x];
}
ans+=(deep[x]>deep[y])?ask_sum(1,tree[y],tree[x]):ask_sum(1,tree[x],tree[y]);
return ans;
}
int main()
{
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
scanf("%d",&n);
for (i=1;i<n;i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x);
for (i=1;i<=n;i++)
scanf("%d",&data[i]);
dfs1(1,0,1);dfs2(1,1);
build(1,1,n);
scanf("%d",&Q);
while (Q)
{
Q--;
scanf("%s%d%d",opt,&x,&y);
if (opt[0]=='C') update(1,tree[x],y-data[x]),data[x]=y;
else if (opt[1]=='M') printf("%d
",find_max(x,y));
else printf("%d
",find_sum(x,y));
}
return 0;
}