poj 2763 Housewife Wind(LCA回転RMQ+ツリー配列)
3514 ワード
标题:1本の木に、2種類の操作:
1、2点間の経路長を求める
2、パスの長さを変更します.
操作1については、まず2点のLCAを求め、d[i]をノードiからルートノードまでの距離とすると、2点経路長はd[u]+d[c]-2*d[lca(u,v)]に等しく、LCAをRMQに変換して求める.
操作2の場合、修正後の操作1への影響、すなわち修正後、その辺のいずれかの端点をルートとするサブツリー内のすべてのノードのdが変化することを考慮する.
ノードuのdfsシーケンス、uに遡るdfsシーケンスをL[u],R[u]でそれぞれ表すと、あるエッジを修正する際に、そのエッジdfsシーケンスが大きい端点をuとすると、dが影響を受ける頂点は、dfsシーケンスが区間[L[u],R[u]]に位置するすべての頂点である.したがって、区間の値は、ツリー配列(またはセグメントツリーなど)で維持することが考えられる.各頂点のdfsシーケンスに対して重み値が与えられ、0に初期化される.各頂点uは、ルートノードまでの距離が区間[0,L[u]]の和である
各エッジiについて、そのdfsシーケンスが大きいその端点をG[i]とし、更新のたびにL[G[i]]の重み値にw(更新された値)を1つ加え、R[G[i]]+1の重み値からwを1つ減算することで、L[G[i]~R[G[i]区間内のすべての頂点が和を求めるときと(すなわち、このノードからルートまでの距離)がw増加し、区間外のノードは影響を受けない.
1、2点間の経路長を求める
2、パスの長さを変更します.
操作1については、まず2点のLCAを求め、d[i]をノードiからルートノードまでの距離とすると、2点経路長はd[u]+d[c]-2*d[lca(u,v)]に等しく、LCAをRMQに変換して求める.
操作2の場合、修正後の操作1への影響、すなわち修正後、その辺のいずれかの端点をルートとするサブツリー内のすべてのノードのdが変化することを考慮する.
ノードuのdfsシーケンス、uに遡るdfsシーケンスをL[u],R[u]でそれぞれ表すと、あるエッジを修正する際に、そのエッジdfsシーケンスが大きい端点をuとすると、dが影響を受ける頂点は、dfsシーケンスが区間[L[u],R[u]]に位置するすべての頂点である.したがって、区間の値は、ツリー配列(またはセグメントツリーなど)で維持することが考えられる.各頂点のdfsシーケンスに対して重み値が与えられ、0に初期化される.各頂点uは、ルートノードまでの距離が区間[0,L[u]]の和である
各エッジiについて、そのdfsシーケンスが大きいその端点をG[i]とし、更新のたびにL[G[i]]の重み値にw(更新された値)を1つ加え、R[G[i]]+1の重み値からwを1つ減算することで、L[G[i]~R[G[i]区間内のすべての頂点が和を求めるときと(すなわち、このノードからルートまでの距離)がw増加し、区間外のノードは影響を受けない.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
#define maxn 100001
struct Edge{
int to,next,w;
}edge[maxn<<1];
int n,a[maxn],head[maxn],dep[maxn<<1],cnt,pos[maxn],E[maxn<<1],dfn,f[maxn<<1][20];
int W[maxn],L[maxn],R[maxn],dfs_clock,C[maxn],G[maxn];
inline void add(int u,int v,int w)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].w=w;
head[u]=cnt++;
}
inline int lowbit(int x){return (x)&(-x);}
void init()
{
memset(head,-1,sizeof(head));
memset(pos,-1,sizeof(pos));
memset(C,0,sizeof(C));
cnt=dfn=0;
dfs_clock=0;
}
void dfs(int u,int deep)
{
E[dfn]=u,dep[dfn]=deep,pos[u]=dfn++;
L[u]=++dfs_clock;
for(int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(pos[v]==-1)
{
G[edge[i].w]=v;
dfs(v,deep+1);
E[dfn]=u,dep[dfn++]=deep;
}
}
R[u]=dfs_clock;
}
void init_RMQ(int n)
{
for(int i=1;i<=n;++i) f[i][0]=i;
for(int j=1;(1<<j)<=n;++j)
for(int i=1;i+(1<<j)-1<=n;++i)
{
if(dep[f[i][j-1]]<dep[f[i+(1<<(j-1))][j-1]]) f[i][j]=f[i][j-1];
else f[i][j]=f[i+(1<<(j-1))][j-1];
}
}
inline int RMQ(int L,int R)
{
int k=0;
while(1<<(k+1)<=R-L+1) ++k;
if(dep[f[L][k]]<dep[f[R-(1<<k)+1][k]]) return f[L][k];
return f[R-(1<<k)+1][k];
}
inline int lca(int u,int v)
{
if(pos[u]>pos[v]) return E[RMQ(pos[v],pos[u])];
return E[RMQ(pos[u],pos[v])];
}
inline void update(int i,int x)
{
for(;i<=n;i+=lowbit(i)) C[i]+=x;
}
inline int sum(int i)
{
int s=0;
for(;i>0;i-=lowbit(i)) s+=C[i];
return s;
}
int main()
{
int i,u,v,k,q,w,s;
while(~scanf("%d%d%d",&n,&q,&s))
{
init();
for(i=1;i<n;++i)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,i);
add(v,u,i);
W[i]=w;
}
dfs(1,0);
init_RMQ(2*n-1);
u=s;
for(i=1;i<n;++i)
{
update(L[G[i]],W[i]);
update(R[G[i]]+1,-W[i]);
}
while(q--)
{
scanf("%d",&k);
if(k){
scanf("%d%d",&u,&w);
update(L[G[u]],w-W[u]);
update(R[G[u]]+1,-w+W[u]);
W[u]=w;
}
else{
scanf("%d",&v);
printf("%d
",sum(L[s])+sum(L[v])-2*sum(L[lca(s,v)]));
s=v;
}
}
}
return 0;
}