本文共 3319 字，大约阅读时间需要 11 分钟。
study from:
http://www.cnblogs.com/chinhhh/p/7965433.html
https://www.luogu.org/problemnew/show/P3384
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define nl 2.7182818284 23 //const ll mod=1e9+7;//998244353 24 const int maxn=1e5+10; 25 26 struct node 27 { 28 int d; 29 node *next; 30 }*e[maxn]; 31 32 ll mod,tag[maxn<<2],sum[maxn<<2]; 33 int dep[maxn],siz[maxn],fa[maxn]={ 0},son[maxn],id[maxn],top[maxn],num=0,n; 34 bool vis[maxn]={ 0}; 35 ll v[maxn],point_num=0,old_id[maxn]; 36 37 void dfs1(int d,int deep) 38 { 39 node *p=e[d]; 40 int maxson=0,dd; 41 vis[d]=1; 42 dep[d]=deep; 43 siz[d]=1; 44 while (p) 45 { 46 dd=p->d; 47 if (!vis[dd]) 48 { 49 fa[dd]=d; 50 dfs1(dd,deep+1); 51 siz[d]+=siz[dd]; 52 if (siz[dd]>maxson) 53 son[d]=dd,maxson=siz[dd]; 54 } 55 p=p->next; 56 } 57 } 58 59 void dfs2(int d,int topd) 60 { 61 id[d]=++num; 62 top[d]=topd; 63 old_id[num]=d; 64 if (son[d]!=0) 65 { 66 dfs2(son[d],topd); 67 node *p=e[d]; 68 int dd; 69 while (p) 70 { 71 dd=p->d; 72 if (dd!=fa[d] && dd!=son[d]) 73 dfs2(dd,dd); 74 p=p->next; 75 } 76 } 77 } 78 79 void build(int index,int l,int r) 80 { 81 tag[index]=0; 82 if (l==r) 83 { 84 // scanf("%lld",&sum[index]); 85 sum[index]=v[old_id[++point_num]]; 86 // sum[index]=sum[index]%mod; 87 } 88 else 89 { 90 int m=(l+r)>>1; 91 build(index<<1,l,m); 92 build(index<<1|1,m+1,r); 93 sum[index]=(sum[index<<1]+sum[index<<1|1])%mod; 94 } 95 } 96 97 void push_down(int index,int len) 98 { 99 tag[index<<1]=(tag[index]+tag[index<<1])%mod;100 tag[index<<1|1]=(tag[index]+tag[index<<1|1])%mod;101 sum[index<<1]=(tag[index]*((len+1)>>1)+sum[index<<1])%mod;102 sum[index<<1|1]=(tag[index]*(len>>1)+sum[index<<1|1])%mod;103 tag[index]=0;104 }105 106 void update(int index,int l,int r,int x,int y,ll k)107 {108 if (x<=l && r<=y)109 {110 sum[index]=(k*(r-l+1)+sum[index])%mod;111 tag[index]=(k+tag[index])%mod;112 return;113 }114 if (tag[index]!=0)115 push_down(index,r-l+1);116 int m=(l+r)>>1;117 if (x<=m)118 update(index<<1,l,m,x,y,k);119 if (m y)129 return 0;130 if (tag[index]!=0)131 push_down(index,r-l+1);132 int m=(l+r)>>1;133 return (query(index<<1,l,m,x,y)+query(index<<1|1,m+1,r,x,y))%mod;134 }135 136 void work1(int x,int y,ll k)137 {138 while (top[x]!=top[y])139 {140 if (dep[top[x]] d=y;189 p->next=e[x];190 e[x]=p;191 192 p=(node*) malloc (sizeof(node));193 p->d=x;194 p->next=e[y];195 e[y]=p;196 }197 198 dfs1(root,0);199 dfs2(root,root); ///two root200 build(1,1,n);201 202 while (q--)203 {204 scanf("%d",&mode);205 if (mode==1)206 {207 scanf("%d%d%lld",&x,&y,&k);208 work1(x,y,k);209 }210 else if (mode==2)211 {212 scanf("%d%d",&x,&y);213 printf("%lld\n",work2(x,y));214 }215 else if (mode==3)216 {217 scanf("%d%lld",&x,&k);218 work3(x,k);219 }220 else221 {222 scanf("%d",&x);223 printf("%lld\n",work4(x));224 }225 }226 return 0;227 }228 /*229 5 100 2 10000000230 0 0 0 0 0231 1 2232 1 5233 3 1234 4 1235 1 5 4 1236 1 2 5 1237 2 4 5238 */
转载于:https://www.cnblogs.com/cmyg/p/9568334.html