POJ 2763 (树链剖分+边修改+边查询）-白红宇

POJ 2763 (树链剖分+边修改+边查询）

阅读量：7158 次

发布时间：2019-06-29

本文共 2782 字，大约阅读时间需要 9 分钟。

题目链接：

题目大意：某人初始在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[2*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]=1;fa[u]=pre;dep[u]=d;    for(int i=head[u];i!=-1;i=e[i].next)    {        int v=e[i].to;        if(v==pre) continue;        dfs1(v,u,d+1);        s[u]+=s[v];        if(son[u]!=-1||s[v]>s[son[u]]) son[u]=v;    }}void dfs2(int u,int tp){    w[u]=++cnt;top[u]=tp;    if(son[u]==-1) return;    dfs2(son[u],tp);    for(int i=head[u];i!=-1;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|1int sum[maxn<<2];void PushUp(int root){    sum[root]=sum[root<<1]+sum[root<<1|1];}void Build(int l,int r,int root){    if(l==r)    {        sum[root]=val[l];        return;    }    int mid=(l+r)>>1;    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)>>1;    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)>>1;    int ret=0;    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,1,n,1);    else Update(w[edge[x].v],v,1,n,1);}int query(int x,int y){    int ans=0;    while(top[x]!=top[y])    {        if(dep[top[x]]
     
      dep[y]) swap(x,y);    if(x!=y) ans+=Query(w[son[x]],w[y],1,n,1);//    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,-1,sizeof(son));        memset(head,-1,sizeof(head));        cnt=tol=0;        for(int i=1;i
      
       dep[edge[i].v]) val[w[edge[i].u]]=edge[i].c;            else val[w[edge[i].v]]=edge[i].c;        }        Build(1,n,1);        while(m--)        {            scanf("%d",&cmd);            if(cmd==0)            {                scanf("%d",&t);                printf("%d\n",query(s,t));                s=t;            }            if(cmd==1)            {                scanf("%d%d",&u,&t);                Change(u,t);            }        }    }}