你RP不好吧。。。。。
by ezoixx130 @ 2017-08-16 07:31:01
百度上可能错了
by Henry_he @ 2017-08-16 07:32:31
你RP不好吧。。。。。
by gzh01 @ 2017-08-16 07:57:30
树剖套线段树代码太恶心长。我的50也调不出来
by MifuneShioriko @ 2017-10-03 16:25:46
树的初值不能这样赋值的说。。。
代码给你，看看我的内个a[real[l]]的赋值
···cpp
```cpp
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson k<<1
#define rson k<<1|1
#define lt(k) tree[k].left
#define rt(k) tree[k].right
#define vl(k) tree[k].value
#define ct(k) tree[k].cnt
#define hd(k) node[k].head
#define fa(k) node[k].father
#define sn(k) node[k].son
#define id(k) node[k].index
#define dp(k) node[k].deep
#define sz(k) node[k].size
#define tp(k) node[k].top
#define fr(k) edge[k].from
#define to(k) edge[k].to
#define nx(k) edge[k].next
void init();
void work();
void addedge(long long ,long long ,long long );
void dfs1(long long ,long long );
void dfs2(long long ,long long );
void build(long long ,long long ,long long );
void update(long long ,long long ,long long ,long long);
void solve2(long long ,long long ,long long );
void pushdown(long long );
void pushup(long long );
long long query(long long ,long long ,long long);
long long solve1(long long ,long long );
const long long maxn=100010;
long long n,m,r,p,a[maxn],real[maxn],x,y,v,flag,total=0;
struct tree
{
long long left,right,cnt,value;
}tree[maxn<<2];
struct node
{
long long head,deep,size,father,son,top,index;
}node[maxn];
struct edge
{
long long from,to,next;
}edge[maxn<<1];
long long read()
{
char ch=getchar();
long long f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void init()
{
memset(node, 0, sizeof(node));
memset(edge, 0, sizeof(edge));
memset(tree, 0, sizeof(tree));
n=read();
m=read();
for (long long i=1;i<=n;i++)
a[i]=read();
for (long long i=1;i<n;i++)
{
x=read();
y=read();
addedge(x,y,i);
addedge(y,x,i+n);
}
dfs1(1,1);
dfs2(1,1);
}
void addedge(long long x,long long y,long long k)
{
fr(k)=x;
to(k)=y;
nx(k)=hd(x);
hd(x)=k;
}
void dfs1(long long k,long long _dp)
{
dp(k)=_dp;
sz(k)=1;
for (long long i=hd(k);i;i=nx(i))
{
if (sz(to(i))) continue;
fa(to(i))=k;
dfs1(to(i),_dp+1);
sz(k)+=sz(to(i));
if (sz(sn(k))<sz(to(i))) sn(k)=to(i);
}
}
void dfs2(long long k,long long _tp)
{
tp(k)=_tp;
id(k)=++total;
real[total]=k;
if (sn(k)) dfs2(sn(k),_tp);
for (long long i=hd(k);i;i=nx(i))
if (!id(to(i))) dfs2(to(i),to(i));
}
void work()
{
build(1,1,n);
for (long long i=1;i<=m;i++)
{
flag=read();
if (flag==3)
{
x=read();
printf("%lld\n",solve1(1,x));
}
else if (flag==1)
{
x=read();
y=read();
update(1,id(x),id(x),y);
}
else
{
x=read();
y=read();
update(1,id(x),id(x)+sz(x)-1,y);
}
}
}
void pushup(long long k)
{
vl(k)=vl(lson)+vl(rson);
}
void pushdown(long long k)
{
if (ct(k))
{
ct(lson)+=ct(k);
ct(rson)+=ct(k);
vl(lson)+=ct(k)*(rt(lson)-lt(lson)+1);
vl(rson)+=ct(k)*(rt(rson)-lt(rson)+1);
ct(k)=0;
}
}
void build(long long k,long long l,long long r)
{
lt(k)=l;
rt(k)=r;
ct(k)=0;
if (l==r)
{
vl(k)=a[real[l]];
return;
}
long long mid=(l+r)>>1;
build(lson,l,mid);
if (r>mid) build(rson,mid+1,r);
pushup(k);
}
void update(long long k,long long l,long long r,long long v)
{
if (l<=lt(k) && rt(k)<=r)
{
ct(k)+=v;
vl(k)+=v*(rt(k)-lt(k)+1);
return;
}
pushdown(k);
if (l<=rt(lson)) update(lson,l,r,v);
if (r>=lt(rson)) update(rson,l,r,v);
pushup(k);
}
long long query(long long k,long long l,long long r)
{
if (l<=lt(k) && rt(k)<=r) return vl(k);
pushdown(k);
long long ans=0;
if (l<=rt(lson)) ans+=query(lson,l,r);
if (r>=lt(rson)) ans+=query(rson,l,r);
return ans;
}
long long solve1(long long u,long long v)
{
long long f1=tp(u),f2=tp(v),ans=0;
while (f1!=f2)
{
if (dp(f1)<dp(f2))
{
swap(f1,f2);
swap(u,v);
}
ans+=query(1,id(f1),id(u));
u=fa(f1);
f1=tp(u);
}
if (dp(u)<dp(v)) swap(u,v);
return ans+query(1,id(v),id(u));
}
void solve2(long long u,long long v,long long w)
{
long long f1=tp(u),f2=tp(v);
while (f1!=f2)
{
if (dp(f1)<dp(f2))
{
swap(f1,f2);
swap(u,v);
}
update(1,id(f1),id(u),w);
u=fa(f1);
f1=tp(u);
}
if (dp(u)<dp(v)) swap(u,v);
update(1,id(v),id(u),w);
}
int main()
{
init();
work();
return 0;
}
…
```
by 如我西沉 @ 2017-11-07 01:59:45