洛谷——P2590 [ZJOI2008]树的统计

https://www.luogu.org/problem/show?pid=2590#sub

题目描述

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。

我们将以下面的形式来要求你对这棵树完成一些操作：

I. CHANGE u t : 把结点u的权值改为t

II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值

III. QSUM u v: 询问从点u到点v的路径上的节点的权值和

注意：从点u到点v的路径上的节点包括u和v本身

输入输出格式

输入格式：

输入文件的第一行为一个整数n，表示节点的个数。

接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。

接下来一行n个整数，第i个整数wi表示节点i的权值。

接下来1行，为一个整数q，表示操作的总数。

接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。

输出格式：

对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

输入输出样例

输入样例#1：

4

1 2

2 3

4 1

4 2 1 3

12

QMAX 3 4

QMAX 3 3

QMAX 3 2

QMAX 2 3

QSUM 3 4

QSUM 2 1

CHANGE 1 5

QMAX 3 4

CHANGE 3 6

QMAX 3 4

QMAX 2 4

QSUM 3 4

输出样例#1：

说明

对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

树剖模板

 #include <algorithm>

 #include <string>

 #include <cstdio>

 using namespace std;

 const int N(+);

 int n,u,v,val[N],q;

 char op[];

 int head[N],sumedge;

 struct Edge

 {

     int u,v,next;

     Edge(int u=,int v=,int next=):

         u(u),v(v),next(next){}

 }edge[N<<];

 void ins(int u,int v)

 {

     edge[++sumedge]=Edge(u,v,head[u]);

     head[u]=sumedge;

 }

 int cnt,id[N],dfn[N],size[N],son[N],top[N],dad[N],deep[N];

 void DFS(int u,int father,int deepth)

 {

     deep[u]=deepth;

     dad[u]=father;

     size[u]=;

     son[u]=;

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

     {

         int to=edge[i].v;

         if(dad[u]==to) continue;

         DFS(to,u,deepth+);    size[u]+=size[to];

         if(!son[u]||size[son[u]]<size[to]) son[u]=to;

     }

 }

 void DFS_(int u,int Top)

 {

     top[u]=Top;

     id[u]=++cnt;

     dfn[cnt]=u;

     if(son[u]) DFS_(son[u],Top);

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

     {

         int to=edge[i].v;

         if(to!=dad[u]&&to!=son[u]) DFS_(to,to);

     }

 }

 struct Tree

 {

     int l,r,mid,sumval,maxval;

 }tree[N<<];

 void Tree_up(int now)

 {

     tree[now].sumval=tree[now<<].sumval+tree[now<<|].sumval;

     tree[now].maxval=max(tree[now<<].maxval,tree[now<<|].maxval);

 }

 void Tree_build(int now,int l,int r)

 {

     tree[now].l=l;tree[now].r=r;

     if(l==r)

     {

         tree[now].maxval=val[dfn[l]];

         tree[now].sumval=val[dfn[l]];

         return ;

     }

     tree[now].mid=l+r>>;

     Tree_build(now<<,l,tree[now].mid);

     Tree_build(now<<|,tree[now].mid+,r);

     Tree_up(now);

 }

 void Tree_change(int now,int to,int x)

 {

     if(tree[now].l==tree[now].r)

     {

         tree[now].maxval=x;

         tree[now].sumval=x;

         return ;

     }

     if(tree[now].mid>=to) Tree_change(now<<,to,x);

     else if(tree[now].mid<to) Tree_change(now<<|,to,x);

     Tree_up(now);

 }

 int Tree_querymax(int now,int l,int r)

 {

     if(tree[now].l==l&&tree[now].r==r) return tree[now].maxval;

     if(tree[now].mid>=r) return Tree_querymax(now<<,l,r);

     else if(tree[now].mid<l) return Tree_querymax(now<<|,l,r);

     else return max(Tree_querymax(now<<,l,tree[now].mid),Tree_querymax(now<<|,tree[now].mid+,r));

 }

 int Tree_querysum(int now,int l,int r)

 {

     if(tree[now].l==l&&tree[now].r==r) return tree[now].sumval;

     if(tree[now].mid>=r) return Tree_querysum(now<<,l,r);

     else if(tree[now].mid<l) return Tree_querysum(now<<|,l,r);

     else return Tree_querysum(now<<,l,tree[now].mid)+Tree_querysum(now<<|,tree[now].mid+,r);

 }

 int List_querymax(int x,int y)

 {

     int ret=-1e9;

     for(;top[x]!=top[y];x=dad[top[x]])

     {

         if(deep[top[x]]<deep[top[y]]) swap(x,y);

         ret=max(ret,Tree_querymax(,id[top[x]],id[x]));

     }

     if(id[x]>id[y]) swap(x,y);

     ret=max(ret,Tree_querymax(,id[x],id[y]));

     return ret;

 }

 int List_querysum(int x,int y)

 {

     int ret=;

     for(;top[x]!=top[y];x=dad[top[x]])

     {

         if(deep[top[x]]<deep[top[y]]) swap(x,y);

         ret+=Tree_querysum(,id[top[x]],id[x]);

     }

     if(id[x]>id[y]) swap(x,y);

     ret+=Tree_querysum(,id[x],id[y]);

     return ret;

 }

 int main()

 {

     scanf("%d",&n);

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

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

     for(int i=;i<=n;i++) scanf("%d",val+i);

     DFS(,,);DFS_(,);

     Tree_build(,,n);

     scanf("%d",&q);

     for(;q--;)

     {

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

         if(op[]=='C') Tree_change(,id[u],v);

         else if(op[]=='M') printf("%d\n",List_querymax(u,v));

         else printf("%d\n",List_querysum(u,v));

     }

     return ;

 }

巴特西

洛谷——P2590 [ZJOI2008]树的统计

https://www.luogu.org/problem/show?pid=2590#sub

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章