#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define R register
int q[
200007];
int n,m,r,mod;
//Segment tree
struct ahh{
int l,r,tag;
long long v;
}a[1600007];
void build(
int ll,
int rr,
int i)
{
a[i].l=
ll;
a[i].r=
rr;
if(ll==rr){a[i].v=q[ll]%mod;
return;}
int mid=(ll+rr)>>
1;
build(ll,mid,(i<<
1));
build(mid+
1,rr,((i<<
1)|
1));
a[i].v=(a[(i<<
1)].v+a[((i<<
1)|
1)].v)%
mod;
return;
}
int ad;
void add(
int ll,
int rr,
int i)
{
if(ll==a[i].l&&rr==a[i].r){a[i].tag+=ad;
return;}
a[i].v=(a[i].v+(rr-ll+
1)*ad)%
mod;
int mid=(a[i].l+a[i].r)>>
1;
if(rr<=mid)add(ll,rr,(i<<
1));
else if(ll>=mid+
1)add(ll,rr,((i<<
1)|
1));
else{add(ll,mid,(i<<
1));add(mid+
1,rr,((i<<
1)|
1));}
return;
}
void pushtag(
int i)
{
if(!a[i].tag)
return;
a[i].v=(a[i].v+(a[i].r-a[i].l+
1)*ad)%
mod;
if(a[i].l==a[i].r){a[i].tag=
0;
return;}
a[(i<<
1)].tag+=
a[i].tag;
a[((i<<
1)|
1)].tag+=
a[i].tag;
a[i].tag=
0;
return;
}
int find(
int ll,
int rr,
int i)
{
pushtag(i);
if(a[i].l==ll&&a[i].r==rr)
return a[i].v;
int mid=(a[i].l+a[i].r)>>
1;
if(rr<=mid)
return (find(ll,rr,(i<<
1)))%
mod;
else if(ll>=mid+
1)
return (find(ll,rr,((i<<
1)|
1)))%
mod;
else return (find(ll,mid,(i<<
1))+find(mid+
1,rr,((i<<
1)|
1)))%
mod;
}
//build tree
int s[
100007];
struct emm{
int e,f;
}b[200007];
int h[
100007];
int cc=
0;
void con(
int x,
int y)
{
b[++cc].f=
h[x];
h[x]=
cc;
b[cc].e=
y;
return;
}
int fa[
100007];
int siz[
100007];
int mac[
100007];
int z[
100007];
int d[
100007];
void dfs(
int x)
{
//int flag=0;
siz[x]=
1;
for(
int i=h[x];i;i=
b[i].f)
if(!
d[b[i].e])
{
// flag++;
fa[b[i].e]=
x;
d[b[i].e]=d[x]+
1;
dfs(b[i].e);
siz[x]+=
siz[b[i].e];
if(siz[b[i].e]>
mac[x])
{
mac[x]=
siz[b[i].e];
z[x]=
b[i].e;
}
}
return;
}
int tot=
0;
int in[
100007];
int out[
100007];
int top[
100007];
void dfss(
int x,
int tp)
{
q[++tot]=
s[x];
in[x]=
tot;
top[x]=
tp;
//if(!z[x]){q[++tot]=x;out[x]=tot;return;}
if(z[x])dfss(z[x],tp);
for(
int i=h[x];i;i=
b[i].f)
if(b[i].e!=fa[x]&&b[i].e!=
z[x])
dfss(b[i].e,b[i].e);
q[++tot]=
s[x];
out[x]=
tot;
return;
}
//Qtree
//int top[100007];
int fitop(
int x)
{
if(z[fa[x]]==x)
return top[x]=
fitop(fa[x]);
return top[x]=
x;
}
void change(
int x,
int y)
{
while(top[x]!=
top[y])
{
if(d[top[x]]>
d[top[y]])swap(x,y);
add(in[top[y]],
in[y],
1);y=
fa[top[y]];
}
if(d[x]>
d[y])swap(x,y);
add(in[y],
in[x],
1);
return;
}
int fin(
int x,
int y)
{
int ans=
0;
while(top[x]!=
top[y])
{
if(d[top[x]]>
d[top[y]])swap(x,y);
ans+=find(
in[top[y]],
in[y],
1);
ans%=
mod;
y=
fa[top[y]];
}
if(d[x]>
d[y])swap(x,y);
ans+=find(
in[y],
in[x],
1);
return ans%
mod;
}
//main
int main()
{
freopen("a.in",
"r",stdin);
scanf("%d%d%d%d",&n,&m,&r,&
mod);
for(R
int i=
1;i<=n;++
i)
{
scanf("%d",&
s[i]);
s[i]%=
mod;
}
for(R
int i=
1;i<=n-
1;++
i)
{
int x,y;
scanf("%d%d",&x,&
y);
con(x,y);
con(y,x);
}
fa[r]=
1,d[r]=
1;
dfs(r);
fa[r]=
0;
dfss(r,r);
build(1,tot,
1);
for(R
int i=
1;i<=n;++
i)
if(!
top[i])fitop(i);
for(R
int i=
1;i<=m;++
i)
{
int ch;
scanf("%d",&
ch);
//cout<<i<<endl;
if(ch==
1)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&
z);
ad=
z;
change(x,y);
}
if(ch==
2)
{
int x,y;
scanf("%d%d",&x,&
y);
printf("%d\n",(fin(x,y))%
mod);
}
if(ch==
3)
{
int x,z;
scanf("%d%d",&x,&
z);
ad=
z;
//cout<<in[x]<<" "<<out[x]<<endl;
add(
in[x],
out[x]-
1,
1);
}
if(ch==
4)
{
int x;
scanf("%d",&
x);
printf("%d\n",find(
in[x],
out[x]-
1,
1)%
mod);
}
}
return 0;
}
大佬也救不活的树剖
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=
3e5;
long long tu[
2][MAXN];
long long hs[
2][MAXN];
long long ps[
2][MAXN];
long long zz[
2][MAXN];
long long hz[
2][MAXN];
long long max(
long long qaq,
long long qwq){
return qaq>qwq?
qaq:qwq;}
int main()
{
int n;
scanf("%d",&
n);
for(
int i=
1;i<=n;++
i)
{
scanf("%d",&tu[
0][i]);
hs[0][i]=hs[
0][i-
1]+tu[
0][i];
}
for(
int i=
1;i<=n;++
i)
{
scanf("%d",&tu[
1][i]);
hs[1][i]=hs[
1][i-
1]+tu[
1][i];
}
int t=-
1;
for(
int i=
1;i<=n;i+=
2)
{
ps[0][i]=ps[
0][i-
1]+(tu[
0][i]*(++
t));
ps[1][i]=ps[
0][i]+(tu[
1][i]*(++
t));
ps[1][i+
1]=ps[
1][i]+(tu[
1][i+
1]*(++
t));
ps[0][i+
1]=ps[
1][i+
1]+(tu[
0][i+
1]*(++
t));
//cout<<ps[0][i]<<" "<<ps[1][i]<<" "<<ps[1][i+1]<<" "<<ps[0][i+1]<<endl;
}
for(
int i=n;i;--
i)
{
zz[0][i]=zz[
0][i+
1]+hs[
0][n]-hs[
0][i-
1];
zz[1][i]=zz[
1][i+
1]+hs[
1][n]-hs[
1][i-
1];
//cout<<zz[0][i]<<" "<<zz[1][i]<<endl;
}
for(
int i=
1;i<=n;++
i)
{
hz[0][i]=(hs[
0][n]-hs[
0][i-
1])*(n-i+
1)-zz[
0][i];
hz[1][i]=(hs[
1][n]-hs[
1][i-
1])*(n-i+
1)-zz[
1][i];
}
long long ans=
0;
for(
int i=
1;i<=n;++
i)
{
ans=max(ans,ps[
0][i-
1]+(i*
2-
1-
1)*(hs[
0][n]-hs[
0][i-
1])+zz[
0][i+
1]+(i+n-
1)*(hs[
1][n]-hs[
1][i-
1])+hz[
1][i]);
cout<<ans<<
endl;
ans=max(ans,ps[
1][i-
1]+(i*
2-
1)*(hs[
1][n]-hs[
1][i-
1])+zz[
1][i+
1]+(i+n-
1)*(hs[
0][n]-hs[
0][i-
1])+hz[
0][i+
1]);
cout<<ans<<
endl;
}
cout<<
ans;
return 0;
}
CF1016C
转载于:https://www.cnblogs.com/qwerta/p/9387501.html
相关资源：JAVA上百实例源码以及开源项目
