SPOJ_6779
这个题目和GSS1的思想是一样的，只不过由于变成了树，所以可以先用树链剖分先将树划分成若干棵线段树再进行求解。
另外我的代码写得确实比较挫，推荐一份效率比较高的用动态树写的代码：。
View Code // 轻重边树链剖分 #include#include #define MAXD 100010#define MAXM 200010#define INF 0x3f3f3f3fint N, a[MAXD], mc[4 * MAXD], lc[4 * MAXD], rc[4 * MAXD], to[4 * MAXD], sum[4 * MAXD];int first[MAXD], e, next[MAXM], v[MAXM];int q[MAXD], fa[MAXD], dep[MAXD], size[MAXD], son[MAXD], top[MAXD], w[MAXD], cnt;void Swap(int &x, int &y){ int t; t = x, x = y, y = t;}int Max(int x, int y){ return x > y ? x : y;}void add(int x, int y){ v[e] = y; next[e] = first[x], first[x] = e ++;}void pushdown(int cur, int x, int y){ if(to[cur] != INF) { int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1; to[ls] = to[rs] = to[cur]; sum[ls] = (mid - x + 1) * to[cur], sum[rs] = (y - mid) * to[cur]; mc[ls] = lc[ls] = rc[ls] = to[cur] > 0 ? sum[ls] : to[cur]; mc[rs] = lc[rs] = rc[rs] = to[cur] > 0 ? sum[rs] : to[cur]; to[cur] = INF; }}void update(int cur, int x, int y){ int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1; sum[cur] = sum[ls] + sum[rs]; mc[cur] = Max(Max(mc[ls], mc[rs]), rc[ls] + lc[rs]); lc[cur] = Max(lc[ls], sum[ls] + lc[rs]); rc[cur] = Max(rc[rs], sum[rs] + rc[ls]);}void refresh(int cur, int x, int y, int s, int t, int v){ int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1; if(x >= s && y <= t) { to[cur] = v; sum[cur] = v * (y - x + 1); mc[cur] = lc[cur] = rc[cur] = v > 0 ? sum[cur] : v; return ; } pushdown(cur, x, y); if(mid >= s) refresh(ls, x, mid, s, t, v); if(mid + 1 <= t) refresh(rs, mid + 1, y, s, t, v); update(cur, x, y);}int Search(int cur, int x, int y, int s, int t, int flag, int &ans, int &ts, int &tc, int tflag){ int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1; if(x >= s && y <= t) { ans = Max(ans, mc[cur]); tc = Max(tc, ts + (tflag == 0 ? lc[cur] : rc[cur])); ts += sum[cur]; return flag == 0 ? lc[cur] : rc[cur]; } pushdown(cur, x, y); if(mid >= t) return Search(ls, x, mid, s, t, 0, ans, ts, tc, tflag); else if(mid + 1 <= s) return Search(rs, mid + 1, y, s, t, 1, ans, ts, tc, tflag); else { int ln, rn; if(tflag == 0) ln = Search(ls, x, mid, s, t, 1, ans, ts, tc, tflag), rn = Search(rs, mid + 1, y, s, t, 0, ans, ts, tc, tflag); else rn = Search(rs, mid + 1, y, s, t, 0, ans, ts, tc, tflag), ln = Search(ls, x, mid, s, t, 1, ans, ts, tc, tflag); ans = Max(ans, ln + rn); if(flag == 0) return Max(lc[ls], sum[ls] + rn); else return Max(rc[rs], sum[rs] + ln); }}void prepare(){ int i, j, k, x, rear = 0; q[rear ++] = 1; dep[1] = 1, fa[1] = 0; for(i = 0; i < rear; i ++) { x = q[i]; for(j = first[x]; j != -1; j = next[j]) if(v[j] != fa[x]) { dep[v[j]] = dep[x] + 1; fa[v[j]] = x; q[rear ++] = v[j]; } } size[0] = 0; for(i = rear - 1; i >= 0; i --) { x = q[i]; son[x] = 0, size[x] = 1; for(j = first[x]; j != -1; j = next[j]) if(v[j] != fa[x]) { size[x] += size[v[j]]; if(size[v[j]] > size[son[x]]) son[x] = v[j]; } } memset(top, 0, sizeof(top)); cnt = 0; for(i = 0; i < rear; i ++) { x = q[i]; if(!top[x]) { j = x; while(j != 0) top[j] = x, w[j] = ++ cnt, j = son[j]; } }}void init(){ int i, j, k, x, y; for(i = 1; i <= N; i ++) scanf("%d", &a[i]); memset(first, -1, sizeof(first)); e = 0; for(i = 1; i < N; i ++) { scanf("%d%d", &x, &y); add(x, y), add(y, x); } prepare(); memset(to, 0x3f, sizeof(to)); for(i = 1; i <= N; i ++) refresh(1, 1, N, w[i], w[i], a[i]);}void query(int x, int y){ int fx = top[x], fy = top[y], cx, cy, ans, ts, tc; cx = cy = ans = 0; while(fx != fy) { if(dep[fx] > dep[fy]) Swap(fx, fy), Swap(x, y), Swap(cx, cy); ts = tc = 0; Search(1, 1, N, w[fy], w[y], 0, ans, ts, tc, 1); ans = Max(ans, tc + cy); ts = tc = 0; Search(1, 1, N, w[fy], w[y], 0, ans, ts, tc, 0); cy = Max(ts + cy, tc); y = fa[fy], fy = top[y]; } if(dep[x] > dep[y]) Swap(x, y), Swap(cx, cy); ts = tc = 0; Search(1, 1, N, w[x], w[y], 0, ans, ts, tc, 0); ans = Max(ans, tc + cx); ts = tc = 0; Search(1, 1, N, w[x], w[y], 0, ans, ts, tc, 1); ans = Max(ans, tc + cy); ans = Max(ans, cx + ts + cy); printf("%d\n", ans);}void change(int x, int y, int v){ int fx = top[x], fy = top[y]; while(fx != fy) { if(dep[fx] > dep[fy]) Swap(x, y), Swap(fx, fy); refresh(1, 1, N, w[fy], w[y], v); y = fa[fy], fy = top[y]; } if(dep[x] > dep[y]) Swap(x, y); refresh(1, 1, N, w[x], w[y], v);}void solve(){ int i, j, a, b, c, op, q; scanf("%d", &q); for(i = 0; i < q; i ++) { scanf("%d%d%d", &op, &a, &b); if(op == 1) query(a, b); else { scanf("%d", &c); change(a, b, c); } }}int main(){ while(scanf("%d", &N) == 1) { init(); solve(); } return 0;}
就这个题目而言，我写的link-cut-tree的代码要比树链剖分快一些，大概有这么两个原因：①树链剖分或者线段树更新的部分我写得太挫了；②用树链剖分写的话，在求解最大连续和的时候本身就比较麻烦，而link-cut-tree求解的时候则很方便。
View Code // link-cut-tree