看错题目了,想成每个城市都可以买一个东西,然后在后面的某个城市卖掉,问最大收益.这个可以类似维护上升序列的方法在O(nlog^3n)的时间复杂度内搞定
这道题用到的一些方法:
1. 可以将有关的线段提取出来,然后一起处理.
2. 线段树可以维护两个方向的信息,这样就可以处理树上有序的东西.
/**************************************************************
Problem: 3999
User: idy002
Language: C++
Result: Accepted
Time:3204 ms
Memory:12144 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define N 50010
using namespace std; typedef long long dnt;
struct Node {
dnt t, b, a[], tag;
int lf, rg;
Node *ls, *rs;
void pushdown() {
if( tag ) {
ls->t += tag;
ls->b += tag;
ls->tag += tag;
rs->t += tag;
rs->b += tag;
rs->tag += tag;
tag = ;
}
}
void update() {
t = max( ls->t, rs->t );
b = min( ls->b, rs->b );
a[] = max( ls->a[], rs->a[] );
a[] = max( a[], rs->t-ls->b );
a[] = max( ls->a[], rs->a[] );
a[] = max( a[], ls->t-rs->b );
}
void modify( int L, int R, int d ) {
if( L<=lf && rg<=R ) {
t += d;
b += d;
tag += d;
return;
}
pushdown();
int mid=(lf+rg)>>;
if( L<=mid ) ls->modify( L, R, d );
if( R>mid ) rs->modify( L, R, d );
update();
}
}pool[N*], *tail=pool, *root; int n, m;
int head[N], dest[N<<], next[N<<], etot;
int aa[N], bb[N];
int fat[N], dep[N], siz[N], son[N], top[N], vid[N];
int qu[N], bg, ed;
Node *su[N], *sv[N];
int tu, tv; void adde( int u, int v ) {
etot++;
dest[etot] = v;
next[etot] = head[u];
head[u] = etot;
}
Node *build( int lf, int rg ) {
Node *nd = ++tail;
if( lf==rg ) {
nd->b = nd->t = bb[lf];
nd->a[] = nd->a[] = ;
nd->lf=lf, nd->rg=rg;
} else {
int mid=(lf+rg)>>;
nd->ls = build( lf, mid );
nd->rs = build( mid+, rg );
nd->lf=lf, nd->rg=rg;
nd->update();
}
return nd;
}
void fetch( Node *nd, int L, int R, Node *(&stk)[N], int &top ) {
int lf=nd->lf, rg=nd->rg;
if( L<=lf && rg<=R ) {
stk[++top] = nd;
return;
}
int mid=(lf+rg)>>;
nd->pushdown();
if( R>mid ) fetch(nd->rs,L,R,stk,top);
if( L<=mid ) fetch(nd->ls,L,R,stk,top);
}
void build_dcp( int s ) {
// fat dep
fat[s] = ;
dep[s] = ;
qu[bg=ed=] = s;
while( bg<=ed ) {
int u=qu[bg++];
for( int t=head[u]; t; t=next[t] ) {
int v=dest[t];
if( v==fat[u] ) continue;
fat[v] = u;
dep[v] = dep[u] + ;
qu[++ed] = v;
}
}
// siz son
for( int i=ed; i>=; i-- ) {
int u=qu[i], p=fat[u];
siz[u]++;
if( p ) {
siz[p] += siz[u];
if( siz[u]>siz[son[p]] ) son[p]=u;
}
}
// top vid
top[s] = s;
vid[s] = ;
for( int i=; i<=ed; i++ ) {
int u=qu[i];
int cur=vid[u]+;
if( son[u] ) {
top[son[u]] = top[u];
vid[son[u]] = cur;
cur += siz[son[u]];
}
for( int t=head[u]; t; t=next[t] ) {
int v=dest[t];
if( v==fat[u] || v==son[u] ) continue;
top[v] = v;
vid[v] = cur;
cur += siz[v];
}
}
// segment
for( int i=; i<=n; i++ )
bb[vid[i]] = aa[i];
root = build( , n );
}
int lca( int u, int v ) {
while( top[u]!=top[v] ) {
if( dep[top[u]]<dep[top[v]] ) swap(u,v);
u = fat[top[u]];
}
return dep[u]<dep[v] ? u : v;
}
dnt query( int u, int v ) {
if( u==v ) return ;
int ca = lca(u,v);
tu = tv = ;
while( top[u]!=top[ca] ) {
fetch(root,vid[top[u]],vid[u],su,tu);
u=fat[top[u]];
}
while( top[v]!=top[ca] ) {
fetch(root,vid[top[v]],vid[v],sv,tv);
v=fat[top[v]];
}
if( u!=ca )
fetch(root,vid[ca],vid[u],su,tu);
else
fetch(root,vid[ca],vid[v],sv,tv);
dnt curt = ;
dnt rt = ;
for( int i=; i<=tv; i++ ) {
rt = max( rt, sv[i]->a[] );
rt = max( rt, curt-sv[i]->b );
curt = max( curt, sv[i]->t );
}
for( int i=tu; i>=; i-- ) {
rt = max( rt, su[i]->a[] );
rt = max( rt, curt-su[i]->b );
curt = max( curt, su[i]->t );
}
return rt;
}
void modify( int u, int v, int d ) {
while( top[u]!=top[v] ) {
if( dep[top[u]]<dep[top[v]] ) swap(u,v);
root->modify(vid[top[u]],vid[u],d);
u=fat[top[u]];
}
if( dep[u]<dep[v] ) swap(u,v);
root->modify(vid[v],vid[u],d);
}
int main() {
scanf( "%d", &n );
for( int i=; i<=n; i++ )
scanf( "%d", aa+i );
for( int i=,u,v; i<n; i++ ) {
scanf( "%d%d", &u, &v );
adde( u, v );
adde( v, u );
}
build_dcp();
scanf( "%d", &m );
for( int t=,u,v,d; t<=m; t++ ) {
scanf( "%d%d%d", &u, &v, &d );
printf( "%lld\n", query(u,v) );
modify(u,v,d);
}
}