P3384 【模板】树链剖分

题目描述

如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

操作1：格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z

操作2：格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和

操作3：格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z

操作4：格式： 4 x 表示求以x为根节点的子树内所有节点值之和

输入输出格式

输入格式：

第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。

接下来一行包含N个非负整数，分别依次表示各个节点上初始的数值。

接下来N-1行每行包含两个整数x、y，表示点x和点y之间连有一条边（保证无环且连通）

接下来M行每行包含若干个正整数，每行表示一个操作，格式如下：

操作1： 1 x y z

操作2： 2 x y

操作3： 3 x z

操作4： 4 x

输出格式：

输出包含若干行，分别依次表示每个操作2或操作4所得的结果（对P取模）

输入输出样例

输入样例#1：

输出样例#1：

2
21

说明

时空限制：1s，128M

数据规模：

对于30%的数据：N<=10，M<=10

对于70%的数据：N<=1000，M<=1000

对于100%的数据：N<=100000，M<=100000

（其实，纯随机生成的树LCA+暴力是能过的，可是，你觉得可能是纯随机的么233）

样例说明：

树的结构如下：

技术分享

各个操作如下：

技术分享

故输出应依次为2、21(重要的事情说三遍：记得取模)

半夜不适合敲代码，尤其这种结构体数组中多个定义的……

码程四十分钟，调程三小时……

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 int n,m,r,p,cnt,tot;
  7 int val[100010],head[100010];
  8 struct data{
  9     int next,to;
 10 }edge[200010];
 11 struct dt{
 12     int fa,son,size,deep,top,num,end;
 13     //son 重儿子 
 14     //size 子结点个数
 15     //top  当前结点所在链的顶结点 
 16 }tree[100010];
 17 struct tr{
 18     int sum,mark;
 19 }segtree[400010];
 20 void add_edge(int start,int ed){
 21     edge[++cnt].next=head[start];
 22     edge[cnt].to=ed;
 23     head[start]=cnt;
 24     return;
 25 }
 26 void dfs_weight(int u){
 27     tree[u].size=1;
 28     tree[u].son=0;
 29     for(int i=head[u];i;i=edge[i].next)
 30         if(edge[i].to!=tree[u].fa){
 31             tree[edge[i].to].fa=u;
 32             tree[edge[i].to].deep=tree[u].deep+1;
 33             dfs_weight(edge[i].to);
 34             tree[u].size+=tree[edge[i].to].size;
 35             if(tree[edge[i].to].size>tree[tree[u].son].size) tree[u].son=edge[i].to;
 36         }
 37     return;
 38 }
 39 void dfs_build(int u,int tp){
 40     tree[u].top=tp;
 41     tree[u].num=++tot;
 42     if(tree[u].son){
 43         dfs_build(tree[u].son,tp);
 44         for(int i=head[u];i;i=edge[i].next)
 45             if(edge[i].to!=tree[u].fa&&edge[i].to!=tree[u].son) dfs_build(edge[i].to,edge[i].to);
 46     }
 47     tree[u].end=tot;
 48     return;
 49 }
 50 void down(int pos,int ll,int mid,int rr){
 51     if(segtree[pos].mark){
 52         segtree[pos<<1].mark+=segtree[pos].mark;
 53         segtree[pos<<1|1].mark+=segtree[pos].mark;
 54         segtree[pos<<1].sum+=(mid-ll+1)*segtree[pos].mark;
 55         segtree[pos<<1].sum%=p;
 56         segtree[pos<<1|1].sum+=(rr-mid)*segtree[pos].mark;
 57         segtree[pos<<1|1].sum%=p;
 58         segtree[pos].mark=0;
 59         return;
 60     }
 61 }
 62 void update(int pl,int pr,int vl,int pos,int ll,int rr){
 63     if(pl<=ll&&pr>=rr){
 64         segtree[pos].mark+=vl;
 65         segtree[pos].sum+=(rr-ll+1)*vl;
 66         segtree[pos].sum%=p;
 67         return;
 68     }
 69     int mid=(ll+rr)>>1;
 70     down(pos,ll,mid,rr);
 71     if(pl<=mid) update(pl,pr,vl,pos<<1,ll,mid);
 72     if(pr>mid) update(pl,pr,vl,pos<<1|1,mid+1,rr);
 73     segtree[pos].sum=segtree[pos<<1].sum+segtree[pos<<1|1].sum;
 74     segtree[pos].sum%=p;
 75     return;
 76 }
 77 void add_val(int aa,int bb,int vl){
 78     int f1=tree[aa].top,f2=tree[bb].top;
 79     while(f1!=f2){
 80         if(tree[f1].deep<tree[f2].deep){
 81             update(tree[f2].num,tree[bb].num,vl,1,1,n);
 82             bb=tree[f2].fa;
 83             f2=tree[bb].top;
 84         }
 85         else{
 86             update(tree[f1].num,tree[aa].num,vl,1,1,n);
 87             aa=tree[f1].fa;
 88             f1=tree[aa].top;
 89         }
 90     }
 91     if(tree[aa].deep<tree[bb].deep) update(tree[aa].num,tree[bb].num,vl,1,1,n);
 92     else update(tree[bb].num,tree[aa].num,vl,1,1,n);
 93     return;
 94 }
 95 int ask(int pl,int pr,int pos,int ll,int rr){
 96     if(pl<=ll&&pr>=rr) return segtree[pos].sum;
 97     int mid=(ll+rr)>>1;
 98     down(pos,ll,mid,rr);
 99     int ans=0;
100     if(pl<=mid){
101         ans+=ask(pl,pr,pos<<1,ll,mid);
102         ans%=p; 
103     }
104     if(pr>mid){
105         ans+=ask(pl,pr,pos<<1|1,mid+1,rr);
106         ans%=p;
107     }
108     return ans;
109 }
110 int ask_some(int aa,int bb){
111     int f1=tree[aa].top,f2=tree[bb].top;
112     int ans=0;
113     while(f1!=f2){
114         if(tree[f1].deep<tree[f2].deep){
115             ans+=ask(tree[f2].num,tree[bb].num,1,1,n);
116             ans%=p;
117             bb=tree[f2].fa;
118             f2=tree[bb].top;
119         }
120         else{
121             ans+=ask(tree[f1].num,tree[aa].num,1,1,n);
122             ans%=p;
123             aa=tree[f1].fa;
124             f1=tree[aa].top;
125         }
126     }
127     if(tree[aa].deep<tree[bb].deep){
128         ans+=ask(tree[aa].num,tree[bb].num,1,1,n);
129         ans%=p;
130     }
131     else{
132         ans+=ask(tree[bb].num,tree[aa].num,1,1,n);
133         ans%=p;
134     }
135     return ans;
136 }
137 int main(){
138     scanf("%d%d%d%d",&n,&m,&r,&p);
139     for(int i=1;i<=n;i++) scanf("%d",&val[i]);
140     int x,y;
141     for(int i=1;i<n;i++){
142         scanf("%d%d",&x,&y);
143         add_edge(x,y);
144         add_edge(y,x);
145     }
146     tree[r].deep=0;
147     dfs_weight(r);
148     dfs_build(r,r);; 
149     for(int i=1;i<=n;i++) update(tree[i].num,tree[i].num,val[i],1,1,n);
150     int od,a,b,c;
151     for(int i=1;i<=m;i++){
152         scanf("%d",&od);
153         if(od==1){
154             scanf("%d%d%d",&a,&b,&c);
155             add_val(a,b,c);
156             continue;
157         }
158         if(od==2){
159             scanf("%d%d",&a,&b);
160             printf("%d\n",ask_some(a,b));
161             continue;
162         }
163         if(od==3){
164             scanf("%d%d",&a,&b);
165             update(tree[a].num,tree[a].end,b,1,1,n);
166             continue;
167         }
168         if(od==4){
169             scanf("%d",&a);
170             printf("%d\n",ask(tree[a].num,tree[a].end,1,1,n));
171             continue;
172         }
173     }
174     return 0;
175 }

树链剖分模板

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 树链剖分模板

树链剖分模板

P3384 【模板】树链剖分

题目描述

输入输出格式

输入输出样例

说明

看完仍有疑问？有类似问题直接问程序猿