题目大意
给出一棵带权有根树，要求完成以下几种操作：
1 u v d 表示将路径 (u,v) 加d (0<=d<=1e8) 2 u v 表示询问路径 (u,v) 上点权绝对值的和
题解
正常树剖，用线段树维护几个信息：绝对值的和，区间内负数的个数，区间内最大的负数 以及 最大的负数所在的位置，因为有区间加操作，所以还要维护一个加标记。
这道题棘手的地方就在于，数字的正负性会随着区间加操作而改变，所以说不能直接维护区间和。所以说观察数据范围 (0<=d<=1e8) 可以得知这道题序列中的所有数字，只会从负变正而不会从正变负，所以说序列内数字的正负性最多只改变n次，所以对于每次数字正负性的变化暴力修改就可以了。
每次处理一个区间加操作之前，先检查区间内进行这个加操作之后是否会有数字的正负性发生改变，也就是说区间内最大的负数改变之后是否大于等于0。如果有的话递归改变那个位置元素的正负性更新线段数，然后再进行加操作。
其他操作与普通树剖线段数无异，祝大家1A。
代码
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxx=
40000008;
char Input[maxx+
5],*ipos;
#define read() (strtol(ipos,&ipos,10))
const int maxn=
int(
1e5)+
11, inf=
1<<
30;
int n,m,v[maxn];
int tot=
0,head[maxn];
struct Edge {
int from,to,next;
Edge() {}
Edge(
int x,
int y,
int nx):from(x),to(y),next(nx) {}
}eage[maxn*
2];
inline void add(
int x,
int y) {
eage[tot]=Edge(x,y,head[x]), head[x]=tot++;
eage[tot]=Edge(y,x,head[y]), head[y]=tot++;
return;
}
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
inline void dfs1(
register int u) {
siz[u]=
1, son[u]=
0;
for(
register int i=head[u];~i;i=eage[i].next)
if(eage[i].to!=fa[u]) {
fa[eage[i].to]=u;
dep[eage[i].to]=dep[u]+
1;
dfs1(eage[i].to);
siz[u]+=siz[eage[i].to];
if(siz[eage[i].to]>siz[son[u]]) son[u]=eage[i].to;
}
}
int top[maxn],seq[maxn],id[maxn],ind;
int val[maxn];
inline void dfs2(
register int u) {
seq[++ind]=u, id[u]=ind;
if(son[fa[u]]==u) top[u]=top[fa[u]];
else top[u]=u;
if(son[u]) dfs2(son[u]);
register int i;
for(i=head[u];~i;i=eage[i].next)
if(eage[i].to!=fa[u] && eage[i].to!=son[u])
dfs2(eage[i].to);
}
#define mp make_pair
#define ls(k) ((k)<<1)
#define rs(k) (ls(k)^1)
#define mid ((l+r)>>1)
struct Node {
long long sum,add;
int len,cnt;
pair<
int,
int> pos;
inline void get_add(
long long);
inline void maintain(
const Node&,
const Node&);
}node[maxn*
4];
inline void Node:: get_add(
long long a) {
sum+=(len-
2*cnt)*a, add+=a;
if(pos.first!=-inf) pos.first+=a;
return;
}
inline void pushdown(
int k) {
Node &ls=node[ls(k)], &rs=node[rs(k)];
long long &add=node[k].add;
if(add) {
ls.get_add(add), rs.get_add(add);
add=
0;
}
return;
}
inline void Node:: maintain(
const Node &a,
const Node &b) {
sum=a.sum+b.sum; add=
0;
len=a.len+b.len; cnt=a.cnt+b.cnt;
pos=max(a.pos,b.pos);
}
inline void build(
int k,
int l,
int r) {
node[k].len=r-l+
1;
if(l==r) {
node[k].sum=(
int)
abs(
1.0*val[l]);
if(val[l]>=
0) node[k].pos=mp(-inf,
0);
else node[k].cnt=
1, node[k].pos=mp(val[l],l);
return;
}
build(ls(k),l,mid);
build(rs(k),mid+
1,r);
node[k].maintain(node[ls(k)],node[rs(k)]);
return;
}
void Build() {
build(
1,
1,n);
return;
}
inline void modify(
int k,
int l,
int r,
int ql,
int qr,
int val) {
if(l!=r) pushdown(k);
if(ql<=l && r<=qr) {
node[k].get_add(val);
return;
}
if(ql<=mid) modify(ls(k),l,mid,ql,qr,val);
if(qr> mid) modify(rs(k),mid+
1,r,ql,qr,val);
node[k].maintain(node[ls(k)],node[rs(k)]);
return;
}
void modify(
int l,
int r,
int a) {
modify(
1,
1,n,l,r,a);
return;
}
inline void flip(
int k,
int l,
int r,
int pos) {
if(l!=r) pushdown(k);
if(l==r) {
node[k].sum*=-
1;
node[k].cnt=
0;
node[k].pos=mp(-inf,
0);
return;
}
if(pos<=mid) flip(ls(k),l,mid,pos);
if(pos> mid) flip(rs(k),mid+
1,r,pos);
node[k].maintain(node[ls(k)],node[rs(k)]);
return;
}
void flip(
int pos) {
flip(
1,
1,n,pos);
return;
}
inline pair<
int,
int> get_pos(
int k,
int l,
int r,
int ql,
int qr) {
if(l!=r) pushdown(k);
if(ql<=l && r<=qr)
return node[k].pos;
pair<
int,
int> res=mp(-inf,
0);
if(ql<=mid) res=max(res,get_pos(ls(k),l,mid,ql,qr));
if(qr> mid) res=max(res,get_pos(rs(k),mid+
1,r,ql,qr));
return res;
}
pair<
int,
int> get_pos(
int l,
int r) {
return get_pos(
1,
1,n,l,r);
}
inline long long query(
int k,
int l,
int r,
int ql,
int qr) {
if(l!=r) pushdown(k);
if(ql<=l && r<=qr)
return node[k].sum;
long long res=
0;
if(ql<=mid) res+=query(ls(k),l,mid,ql,qr);
if(qr> mid) res+=query(rs(k),mid+
1,r,ql,qr);
return res;
}
long long Query(
int l,
int r) {
return query(
1,
1,n,l,r);
}
inline void Modify(
int l,
int r,
int val) {
while(
true) {
pair<
int,
int> pos=get_pos(l,r);
if(pos.first+val>=
0) flip(pos.second);
else break;
}
modify(l,r,val);
return;
}
inline void Tree_modify(
register int u,
register int v,
int a) {
while(top[u]!=top[v]) {
if(dep[top[u]]<dep[top[v]])
std::swap(u,v);
Modify(id[top[u]],id[u],a);
u=fa[top[u]];
}
if(dep[u]>dep[v])
std::swap(u,v);
Modify(id[u],id[v],a);
return;
}
inline long long Tree_query(
int u,
int v) {
long long res=
0;
while(top[u]!=top[v]) {
if(dep[top[u]]<dep[top[v]])
std::swap(u,v);
res+=Query(id[top[u]],id[u]);
u=fa[top[u]];
}
if(dep[u]>dep[v])
std::swap(u,v);
res+=Query(id[u],id[v]);
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen(
"input.txt",
"r",stdin);
freopen(
"output.txt",
"w",stdout);
#endif
fread(Input,maxx,
1,stdin);ipos=Input;
n=read(), m=read();
for(
int i=
1;i<=n;i++) {
head[i]=-
1;
v[i]=read();
}
for(
int x,y,i=
1;i<n;i++) {
x=read(), y=read();
add(x,y);
}
dep[
1]=
1, fa[
1]=-
1;
dfs1(
1),
dfs2(
1);
for(
int i=
1;i<=n;i++)
val[i]=v[seq[i]];
Build();
int op,u,v,a;
for(
int i=
1;i<=m;i++) {
op=read(), u=read(), v=read();
if(op==
1) {
a=read();
Tree_modify(u,v,a);
}
else {
printf(
"%lld\n",Tree_query(u,v));
}
}
return 0;
}
数据生成器：
using namespace std;
const
int n=
int(
1e5),
m=n;
int maxdep=
0;
bool vis[n+
11];
int f[n+
11];
inline
int _find(register
int k) {
if(f[k]==k)
return k;
return f[k]=_find(f[k]);
}
int main() {
freopen(
"input0.txt",
"w",stdout);
srand(
time(NULL));
printf(
"%d %d\n",n,
m);
for(
int i=
1;i<=n;i++) {
int sign=
rand()&
1;
sign=sign?
1:-
1;
printf(
"%d ",sign
*rand());
}
printf(
"\n");
for(
int i=
1;i<=n;i++)
f[i]=i;
int tot=
0;
while(tot<n-
1) {
int u=(
1ll
*rand()
*rand())
%n+
1, v=(
1ll
*rand()
*rand())
%n+
1;
int g1=_find(u), g2=_find(v);
if(g1!=g2) {
f[g1]=g2;
printf(
"%d %d\n",u,v);
tot++;
}
}
for(
int i=
1;i<=
m;i++) {
int op=
rand()
%2+
1;
int u=(
1ll
*rand()
*rand())
%n+
1, v=(
1ll
*rand()
*rand())
%n+
1, d=(
1ll
*rand()
*rand())
%((
int)
1e5)+
1;
if(op==
1)
printf(
"%d %d %d %d\n",op,u,v,d);
else printf(
"%d %d %d\n",op,u,v);
}
return 0;
}
