ツリー分割テンプレート+入門問題SPOJ-QTREE
12253 ワード
タイトルリンク:[クリックしてアクセス](http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=13013)木の鎖の分割は複雑なアルゴリズムやデータ構造ではなく、1本の木を鎖に分解して処理できるだけで、言い換えれば、木の鎖の分割はxxxデータ構造/アルゴリズムの木の上での普及にすぎない.あるいは、木の鎖の分割は木hashをいくつかの連続した区間にしただけだ.例えば、以下のようにこの問題は、ツリーを重鎖と軽鎖に分けて線分ツリーにマッピングし、線分ツリーでクエリーや修正などの操作を行うことです.そのため、ツリーの分割のポイントは2つあります.1つは、ツリーをいくつかのセグメントに正しく分解して線分ツリーにマッピングすることです.2つは、線分ツリーでクエリーや修正操作を行うときに、分解後のツリーの性質に注意することです.次のコードクエリーに対してツリーのエッジを変更し、テンプレートとして使用できます.非常に良いブログ:ツリーチェーン分割
コードは以下の通りです
コードは以下の通りです
#include
#include
#include
using namespace std;
/// ,
///
const int maxn=10010;
struct Edge
{
int to,next;
}edge[maxn*2];
int head[maxn],tot;
int top[maxn];///top[v] v
int fa[maxn]; ///
int deep[maxn]; ///
int num[maxn]; ///num[v] v
int p[maxn];///p[v] v
int fp[maxn]; ///
int son[maxn]; ///son[u] u
int pos;
void init()
{
tot=0;
memset(head,-1,sizeof(head));
pos=0;
memset(son,-1,sizeof(son));
}
///
void addedge(int u,int v)
{
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
/// dfs fa,num,deep,son
void dfs1(int u,int pre,int d)
{
deep[u]=d;
fa[u]=pre;
num[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(v!=pre)
{
dfs1(v,u,d+1);
num[u]+=num[v];
/// u
if(son[u]==-1||num[v]>num[son[u]])
son[u]=v;
}
}
}
/// dfs top p
void getpos(int u,int sp)
{
top[u]=sp;
p[u]=pos++;
fp[p[u]]=u;
if(son[u]==-1) return;
///
getpos(son[u],sp);
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(v!=son[u]&&v!=fa[u]) ///
getpos(v,v);
}
}
///
struct node
{
int l,r;
int Max;
}segTree[maxn*3];
void build(int i,int l,int r)
{
segTree[i].l=l;
segTree[i].r=r;
segTree[i].Max=0;
if(l==r) return;
int mid=(l+r)/2;
build(i<<1,l,mid);
build((i<<1)|1,mid+1,r);
}
void push_up(int i)
{
segTree[i].Max=max(segTree[i<<1].Max,segTree[(i<<1)|1].Max);
}
/// k val
void update(int i,int k,int val)
{
if(segTree[i].l==k&&segTree[i].r==k)
{
segTree[i].Max=val;
return;
}
int mid=(segTree[i].l+segTree[i].r)/2;
if(k<=mid)
update(i<<1,k,val);
else
update((i<<1)|1,k,val);
push_up(i);
}
/// :[l,r]
int query(int i,int l,int r)
{
if(segTree[i].l==l&&segTree[i].r==r)
return segTree[i].Max;
int mid=(segTree[i].l+segTree[i].r)/2;
if(r<=mid) return query(i<<1,l,r);
else if(l>mid) return query((i<<1)|1,l,r);
else return max(query(i<<1,l,mid),query((i<<1)|1,mid+1,r));
}
/// u->v
int find(int u,int v)
{
int f1=top[u];
int f2=top[v];
int tmp=0;
while(f1!=f2)
{
/// deep[f1]>=deep[f2]
if(deep[f1]1,p[f1],p[u]));
u=fa[f1]; f1=top[u];
}
if(u==v) return tmp;
if(deep[u]>deep[v])
swap(u,v);
return max(tmp,query(1,p[son[u]],p[v]));
}
int e[maxn][3];
int main()
{
int T;
int n,u,v;
// freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
init();
scanf("%d",&n);
for(int i=0;i1;i++)
{
scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
///
addedge(e[i][0],e[i][1]);
addedge(e[i][1],e[i][0]);
}
dfs1(1,0,0);
getpos(1,1);
build(1,0,pos-1);
///
for(int i=0;i1;i++)
{
if(deep[e[i][0]]>deep[e[i][1]])
swap(e[i][0],e[i][1]);
update(1,p[e[i][1]],e[i][2]);
}
char op[10];
while(scanf("%s",op))
{
if(op[0]=='D') break;
scanf("%d%d",&u,&v);
if(op[0]=='Q')
printf("%d
",find(u,v)); ///
else
update(1,p[e[u-1][1]],v); ///
}
}
return 0;
}