题目链接:http://poj.org/problem?id=2763
题目大意:某人初始在s点。有q次移动,每次移动沿着树上一条链,每经过一条边有一定花费,这个花费可以任意修改。问每次移动的花费。
解题思路:
树链剖分基础题。每次Q之后改变一下s。
线段树记录的是边权。方法是对于一条边(u,v),边权值加在dep比较大的那一端。
链查询(边)和 链查询(点)在轻链时略有不同。
注意本题使用vector邻接表存图是会TLE的,应该使用链式前向星。树链剖分中使用链式前向星是基本要求。
#include "cstdio"
#include "cstring"
using namespace std;
#define maxn 100005
int s[maxn],dep[maxn],w[maxn],fa[maxn],top[maxn],son[maxn],val[maxn],cnt,tol,n;
int head[maxn];
struct Edge
{
int u,v,c;
}edge[maxn];
struct EDGE
{
int next,to;
}e[*maxn];
void addedge(int u,int v)
{
e[tol].to=v;
e[tol].next=head[u];
head[u]=tol++;
}
void dfs1(int u,int pre,int d)
{
s[u]=;fa[u]=pre;dep[u]=d;
for(int i=head[u];i!=-;i=e[i].next)
{
int v=e[i].to;
if(v==pre) continue;
dfs1(v,u,d+);
s[u]+=s[v];
if(son[u]!=-||s[v]>s[son[u]]) son[u]=v;
}
}
void dfs2(int u,int tp)
{
w[u]=++cnt;top[u]=tp;
if(son[u]==-) return;
dfs2(son[u],tp);
for(int i=head[u];i!=-;i=e[i].next)
{
int v=e[i].to;
if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
}
}
//Segment Tree
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
int sum[maxn<<];
void PushUp(int root)
{
sum[root]=sum[root<<]+sum[root<<|];
}
void Build(int l,int r,int root)
{
if(l==r)
{
sum[root]=val[l];
return;
}
int mid=(l+r)>>;
Build(lson);
Build(rson);
PushUp(root);
}
void Update(int p,int v,int l,int r,int root)
{
if(l==r)
{
sum[root]=v;
return;
}
int mid=(l+r)>>;
if(p<=mid) Update(p,v,lson);
else Update(p,v,rson);
PushUp(root);
}
int Query(int L,int R,int l,int r,int root)
{
if(L<=l&&r<=R) return sum[root];
int mid=(l+r)>>;
int ret=;
if(L<=mid) ret+=Query(L,R,lson);
if(R>mid) ret+=Query(L,R,rson);
return ret;
}
void Change(int x,int v)
{
if(dep[edge[x].u]>dep[edge[x].v]) Update(w[edge[x].u],v,,n,);
else Update(w[edge[x].v],v,,n,);
}
int query(int x,int y)
{
int ans=;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=Query(w[top[x]],w[x],,n,);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
if(x!=y) ans+=Query(w[son[x]],w[y],,n,);//
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
int m,s,u,t,cmd;
while(~scanf("%d%d%d",&n,&m,&s))
{
memset(son,-,sizeof(son));
memset(head,-,sizeof(head));
cnt=tol=;
for(int i=;i<n;i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].c);
addedge(edge[i].u,edge[i].v);
addedge(edge[i].v,edge[i].u);
}
dfs1(,,);
dfs2(,);
for(int i=;i<n;i++)
{
if(dep[edge[i].u]>dep[edge[i].v]) val[w[edge[i].u]]=edge[i].c;
else val[w[edge[i].v]]=edge[i].c;
}
Build(,n,);
while(m--)
{
scanf("%d",&cmd);
if(cmd==)
{
scanf("%d",&t);
printf("%d\n",query(s,t));
s=t;
}
if(cmd==)
{
scanf("%d%d",&u,&t);
Change(u,t);
}
}
}
}
13493821 | neopenx | 2763 | Accepted | 9676K | 1579MS | C++ | 3176B | 2014-10-01 16:16:22 |