题意:
N个城市,由N-1条边连接, 有A,B两人占领i城市,花费分别为 A[i], B[i]. 相邻的则花费减半,(A占领城市x,则与x连通的城市，A再占领则只要A[x]/2, B类似)
解法：
dp[i][j][k] : 表示占领第 i 座城市，
j = 0 则为 A占领
j = 1 则为 B占领
k = 0 则全部花费一半
k = 1 则其子孙节点中存在全额花费的
若此时遍历完 子节点 v，后回到其父节点 u . 有如下情况
一 对于 dp[u][0][0] ， 第u个城市，由A占领，且子孙节点中由A占领的都是付 一半花费，可能有的情况
1. 以u为根的子树，全部被A占领，且全部花费一半，此时为 dp[v][0][0] + A[u]/2
2. 以u为根的子树，存在被B占领，且其必定存在付全额花费的，此时为 dp[v][1][1] + A[u]/2
则最终情况为
dp[u][0][0] = Min { dp[v][0][0], dp[v][1][1] } + A[u]/2
而被B占领的情况,与A类似。
二 对于dp[u][0][1], 第u个城市，被A占领，且存在付全额花费的情况
1. 若是 u节点本身花费全额则为 Min{ dp[v][0][0], dp[v][1][1] } + A[u]
2. 若是 其子孙节点花费全额，则必定是选择一个花费最小的来付全额，则最小花费为
Min{ dp[v][0][1] - Min{dp[v][0][0],dp[v][1][1]} }
则最终情况为
SA = sum{ Min{dp[v][0][0],dp[v][1][1]} }
SB = sum{ Min{dp[v][1][0],dp[v][0][1] } }
DA = Min{ dp[v][0][1] - Min{dp[v][0][0],dp[v][1][1]} }
DB = Min{ dp[v][1][1] - Min{dp[v][1][0],dp[v][0][1]} }
dp[u][0][0] = SA + A[u]/2
dp[u][1][0] = SB + B[u]/2
dp[u][0][1] = Min{ SA+A[u], SA+A[u]/2+DA }
dp[u][1][1] = Min{ SB+B[u], SB+B[u]/2+DB }
View Code
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; #define lson (rt<<1) #define rson (rt<<1|1) const int N = 500010; typedef long long LL; struct Tree{ int l, r; int lx, rx, ml, mr; LL lsum, rsum, msum, sum; }tr[N<<2]; int k[N]; inline void push_up( int rt ){ if( tr[rt].l == tr[rt].r ) return; tr[rt].sum = tr[lson].sum + tr[rson].sum; // WA 了好多次在这， 因为 lsum 不一定到 r, rt.lsum = lson.sum+rson.lsum 左儿子的区间和 if( tr[lson].lsum < tr[lson].sum+tr[rson].lsum ) tr[rt].lsum = tr[lson].sum+tr[rson].lsum,tr[rt].lx = tr[rson].lx; else tr[rt].lsum = tr[lson].lsum, tr[rt].lx = tr[lson].lx; if( tr[rson].rsum < tr[rson].sum+tr[lson].rsum ) tr[rt].rsum = tr[rson].sum+tr[lson].rsum,tr[rt].rx = tr[lson].rx; else tr[rt].rsum = tr[rson].rsum, tr[rt].rx = tr[rson].rx; tr[rt].msum = tr[lson].msum, tr[rt].ml = tr[lson].ml, tr[rt].mr = tr[lson].mr; if( tr[rt].msum <= tr[lson].rsum+tr[rson].lsum ){ if( (tr[rt].msum == tr[lson].rsum+tr[rson].lsum) && (tr[rt].ml > tr[lson].rx) ) tr[rt].ml = tr[lson].rx, tr[rt].mr = tr[rson].lx; else if( tr[rt].msum < tr[lson].rsum+tr[rson].lsum ) tr[rt].msum = tr[lson].rsum + tr[rson].lsum, tr[rt].ml = tr[lson].rx, tr[rt].mr = tr[rson].lx; } if( tr[rt].msum < tr[rson].msum ) tr[rt].msum = tr[rson].msum, tr[rt].ml = tr[rson].ml, tr[rt].mr = tr[rson].mr; // tr[rt].msum = max( max(tr[lson].msum,tr[rson].msum), tr[lson].rsum+tr[rson].lsum ); // printf("rt = %d, (%d,%d)\n", rt, tr[rt].l, tr[rt].r ); // printf("Sum:(%I64d,%I64d,%I64d)\n", tr[rt].lsum, tr[rt].msum, tr[rt].rsum ); // printf("idx:(%d,%d),[%d,%d]\n", tr[rt].lx, tr[rt].rx, tr[rt].ml, tr[rt].mr ); // printf("lsum = %I64d, rsum = %I64d, msum = %I64d\n", tr[rt].lsum, tr[rt].rsum, tr[rt].msum ); } void build( int rt, int l, int r ){ tr[rt].l = l, tr[rt].r = r; if( l == r ){ tr[rt].lsum = tr[rt].rsum = tr[rt].msum = tr[rt].sum = k[l]; tr[rt].lx = tr[rt].rx = tr[rt].ml = tr[rt].mr = l; return; } int m = (l+r)>>1; build( lson, l, m ); build( rson, m+1, r ); push_up(rt); } inline Tree query( int rt, int l, int r ){ if( tr[rt].l == l && tr[rt].r == r ) return tr[rt]; int m = (tr[rt].l+tr[rt].r)>>1; if( r <= m ) return query( lson, l, r ); else if( m < l ) return query( rson, l, r ); else{ Tree t1, t2, t; t1 = query( lson, l, m ); t2 = query( rson, m+1, r ); t.sum = t1.sum + t2.sum; if( t1.lsum < t1.sum+t2.lsum ) t.lsum = t1.sum+t2.lsum, t.lx = t2.lx; else t.lsum = t1.lsum, t.lx = t1.lx; if( t2.rsum < t2.sum+t1.rsum ) t.rsum = t2.sum+t1.rsum, t.rx = t1.rx; else t.rsum = t2.rsum, t.rx = t2.rx; t.msum = t1.msum, t.ml = t1.ml, t.mr = t1.mr; if( t.msum <= t1.rsum+t2.lsum ){ if( (t.msum == t1.rsum+t2.lsum) && (t.ml > t1.rx) ) t.ml = t1.rx, t.mr = t2.lx; else if( t.msum < t1.rsum+t2.lsum ) t.msum = t1.rsum + t2.lsum, t.ml = t1.rx, t.mr = t2.lx; } if( t.msum < t2.msum ) t.msum = t2.msum, t.ml = t2.ml, t.mr = t2.mr; //t.msum = max( max(t1.msum,t2.msum), t1.rsum+t2.lsum ); t.l = l, t.r = r; return t; } } int main(){ freopen("in.txt","r",stdin); freopen("test.txt","w",stdout); int T, n, m; scanf("%d", &T); while( T-- ){ scanf("%d%d", &n,&m); for(int i = 1; i <= n; i++) scanf("%d", &k[i] ); build(1,1,n); int a, b; for(int i = 0; i < m; i++){ scanf("%d%d",&a,&b); Tree t = query( 1, a, b ); // printf("msum = %I64d, ml = %d, mr = %d\n", t.msum, t.ml, t.mr ); printf("%d %d\n", t.ml, t.mr ); } } return 0; }