hdu 3966 Aragorn's Story（树链剖分+树状数组/线段树）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3966

题意：

给出一棵树，并给定各个点权的值，然后有3种操作：

I C1 C2 K: 把C1与C2的路径上的所有点权值加上K

D C1 C2 K：把C1与C2的路径上的所有点权值减去K

Q C：查询节点编号为C的权值

分析：

典型的树链剖分，对节点进行操作，可以用树状数组或者线段树。

树链剖分+树状数组：

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 using namespace std;

 const int maxn = ;

 struct Edge

 {

     int to,next;

 }edge[maxn*];

 int head[maxn],cnt,num;

 int a[maxn],n,m,p,c[maxn];

 int size[maxn],top[maxn],id[maxn],fa[maxn],son[maxn],dep[maxn];

 void init()

 {

     memset(head,-,sizeof(head));

     memset(son,-,sizeof(son));

     memset(c,,sizeof(c));

     cnt=;

     num=;

 }

 void addedge(int u,int v)

 {

     edge[cnt].to = v;

     edge[cnt].next = head[u];

        head[u] = cnt++;

 }

 void dfs_1(int u,int f,int d)

 {

     dep[u]=d;

     size[u]=;

     fa[u]=f;

     for(int i=head[u];i!=-;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==f)

             continue;

         dfs_1(v,u,d+);

         size[u]+=size[v];

         if(son[u]==-||size[son[u]]<size[v])

             son[u]=v;

     }

 }

 void dfs_2(int u,int tp)

 {

     top[u] = tp;

     id[u] = ++num;

     if(son[u]!=-)

         dfs_2(son[u],tp);

     for(int i=head[u];i!=-;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==fa[u]||v==son[u])

             continue;

         dfs_2(v,v);

     }

 }

 int lowbit(int x)

 {

     return x&-x;

 }

 int sum(int x)

 {

     int res=;

     while(x>)

     {

         res+=c[x];

         x-=lowbit(x);

     }

     return res;

 }

 void add(int x,int d)

 {

     while(x<=n)

     {

         c[x]+=d;

         x+=lowbit(x);

     }

 }

 void change(int u,int v,int val)

 {

     int tp1=top[u],tp2=top[v];

     while(tp1!=tp2)

     {

         if(dep[tp1]<dep[tp2])

         {

             swap(tp1,tp2);

             swap(u,v);

         }

         add(id[tp1],val);

         add(id[u]+,-val);

         u=fa[tp1];

         tp1=top[u];

     }

     if(dep[u]>dep[v])

         swap(u,v);

     add(id[u],val);

     add(id[v]+,-val);

 }

 int main()

 {

     while(~scanf("%d%d%d",&n,&m,&p))

     {

         init();

         for(int i=;i<=n;i++)

             scanf("%d",&a[i]);

         for(int i=;i<=m;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             addedge(u,v);

             addedge(v,u);

         }

         dfs_1(,,);

         dfs_2(,);

         for(int i=;i<=n;i++)

         {

             add(id[i],a[i]);

             add(id[i]+,-a[i]);

         }

         char s[];

         int c1,c2,k,c;

         for(int i=;i<p;i++)

         {

             scanf("%s",s);

             if(s[]=='I')

             {

                 scanf("%d%d%d",&c1,&c2,&k);

                 change(c1,c2,k);

             }

             if(s[]=='D')

             {

                 scanf("%d%d%d",&c1,&c2,&k);

                 change(c1,c2,-k);

             }

             if(s[]=='Q')

             {

                 scanf("%d",&c);

                 cout<<sum(id[c])<<endl;

             }

         }

     }

     return ;

 }

树链剖分+线段树：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 using namespace std;

 const int maxn = ;

 int n,m,p;

 int val[maxn],a[maxn];

 struct Edge

 {

     int to,next;

 }edge[maxn*];

 int head[maxn],add[maxn*];

 int dep[maxn],fa[maxn],size[maxn],son[maxn],top[maxn],id[maxn];

 int cnt,num;

 void init()

 {

         memset(head,-,sizeof(head));

     memset(son,-,sizeof(son));

     memset(add,,sizeof(add));

     cnt=;

         num=;

 }

 void addedge(int u,int v)

 {

     edge[cnt].to=v;

     edge[cnt].next=head[u];

     head[u]=cnt++;

 }

 void dfs_1(int u,int f,int d)

 {

     dep[u]=d;

     size[u]=;

     fa[u]=f;

     for(int i=head[u];i!=-;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==f)

             continue;

         dfs_1(v,u,d+);

         size[u]+=size[v];

         if(son[u]==-||size[son[u]]<size[v])

             son[u]=v;

     }

 }

 void dfs_2(int u,int tp)

 {

     top[u] = tp;

     id[u] = ++num;

     if(son[u]!=-)

         dfs_2(son[u],tp);

     for(int i=head[u];i!=-;i=edge[i].next)

     {

         int v = edge[i].to;

         if(v == fa[u] ||v == son[u])

             continue;

         dfs_2(v,v);

     }

 }

 struct Tree

 {

     int left,right;

     int sum;

 }tree[maxn*];

 void pushup(int i)

 {

     tree[i].sum = tree[i*].sum + tree[i*+].sum;

 }

 void build(int i,int begin,int end)

 {

     tree[i].left=begin;

     tree[i].right=end;

     if(begin==end)

     {

         tree[i].sum=val[begin];

         return;

     }

     int mid=(begin+end)/;

     build(i*,begin,mid);

     build(i*+,mid+,end);

     pushup(i);

 }

 void pushdown(int i)

 {

     if(add[i])

     {

         add[i*] += add[i];

         add[i*+] += add[i];

         int mid=(tree[i].left+tree[i].right)/;

         tree[i*].sum += add[i]*(mid-tree[i].left+);

         tree[i*+].sum += add[i]*(tree[i].right-mid);

         add[i]=;

     }

 }

 void update(int i,int begin,int end,int value)

 {

     if(tree[i].left>=begin&&tree[i].right<=end)

     {

         add[i]+=value;

         tree[i].sum+=value*(tree[i].right-tree[i].left+);

         return;

     }

     pushdown(i);

     int mid=(tree[i].left+tree[i].right)/;

     if(mid>=begin)

         update(i*,begin,end,value);

     if(mid<end)

         update(i*+,begin,end,value);

     pushup(i);

 }

 void change(int u,int v,int value)

 {

     int tp1=top[u],tp2=top[v];

     while(tp1!=tp2)

     {

         if(dep[tp1]<dep[tp2])

         {

             swap(tp1,tp2);

             swap(u,v);

         }

         update(,id[tp1],id[u],value);

         u = fa[tp1];

         tp1 = top[u];

     }

     if(dep[u]>dep[v])

         swap(u,v);

     update(,id[u],id[v],value);

 }

 long long query(int i,int begin,int end)

 {

     if(tree[i].left>=begin&&tree[i].right<=end)

         return tree[i].sum;

     pushdown(i);

     int mid=(tree[i].left+tree[i].right)/;

     long long ans=;

     if(mid>=begin)

         ans+=query(i*,begin,end);

     if(mid<end)

         ans+=query(i*+,begin,end);

     return ans;

 }

 int main()

 {

     while(~scanf("%d%d%d",&n,&m,&p))

     {

         init();

         for(int i=;i<=n;i++)

             scanf("%d",&a[i]);

         for(int i=;i<=m;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             addedge(u,v);

             addedge(v,u);

         }

         dfs_1(,,);

         dfs_2(,);

         for(int i=;i<=n;i++)

             val[id[i]]=a[i];

         build(,,n);

         char s[];

         int c1,c2,k,c;

         for(int i=;i<p;i++)

         {

             scanf("%s",s);

             if(s[]=='I')

             {

                 scanf("%d%d%d",&c1,&c2,&k);

                 change(c1,c2,k);

             }

             if(s[]=='D')

             {

                 scanf("%d%d%d",&c1,&c2,&k);

                 change(c1,c2,-k);

             }

             if(s[]=='Q')

             {

                 scanf("%d",&c);

                 cout<<query(,id[c],id[c])<<endl;

             }

         }

     }

     return ;

 }

巴特西

hdu 3966 Aragorn's Story（树链剖分+树状数组/线段树）

最新文章

热门文章