BZOJ1036 - [ZJOI2008]树的统计Count

2016/12/12

题目

给定一颗无向树,每次三种操作:

  1. 路径上点中的最大权值
  2. 路径上点的权值和
  3. 修改第 号点的权值为

SPOJ QTREE 改吧改吧就能A

诶为啥常数这么大!(2996ms

自己写的代码好次啊。

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(_var, _start, _end) for(int _var=_start;_var<=_end;++_var)
#define per(_var, _start, _end) for(int _var=_start;_var>=_end;--_var)
#define out(_var, _cur) for(It _var=Head[_cur];_var;_var=_var->n)
#define CLR(_x) { memset(_x, 0, sizeof(_x)); }
using namespace std;
const int PSIZ = 2E6 + 1E3;
const int _oo  = 1E9;
int N;

struct tgno {
    int v;
    tgno *n;
} POOL[PSIZ]; int ppos;
typedef tgno* It;
It Head[PSIZ];

void _add(int u, int v) {
    POOL[ppos].v = v; POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

void addEdge(int u, int v) { _add(u, v); _add(v, u); }

int dep[PSIZ], siz[PSIZ], fa[PSIZ], son[PSIZ], src[PSIZ];
int top[PSIZ], tid[PSIZ], trank[PSIZ], tpos;

void input() {
    int u, v; int t = 1;
    rep(i, 2, N) { scanf("%d %d", &u, &v); addEdge(u, v); }
    rep(i, 1, N) { scanf("%d", &src[i]); }
}

void dfs1(int cur, int pre, int dd) {
    dep[cur] = dd, fa[cur] = pre, siz[cur] = 1;
    out(i, cur) {
        if(i->v == pre) continue;
        dfs1(i->v, cur, dd+1);
        siz[cur] += siz[i->v];
        if(!son[cur] || siz[i->v] > siz[son[cur]]) {
            son[cur] = i->v;
        }
    }
}

void dfs2(int cur, int tp) {
    top[cur] = tp, tid[cur] = ++tpos; trank[tid[cur]] = cur;
    if(!son[cur]) return;
    dfs2(son[cur], tp);
    out(i, cur) {
        if(i->v != son[cur] && i->v != fa[cur]) {
            dfs2(i->v, i->v);
        }
    }
}

struct zkwseg {
#define lson(x) ((x) << 1)
#define rson(x) (lson(x) | 1)
    int mmax[PSIZ<<2];
    int msum[PSIZ<<2]; int cap, M;
    void mkTree(int c) {
        cap = c; for(M=1;M<cap;M<<=1) {} CLR(mmax);
        rep(i, 1, N) msum[M-1+tid[i]] = mmax[M-1+tid[i]] = src[i];
        per(i, M-1, 1) {
            msum[i] = msum[lson(i)] + msum[rson(i)];
            mmax[i] = max(mmax[lson(i)], mmax[rson(i)]);
        }
    }
    void fix(int pos) {
        pos>>=1;
        for(;pos;pos>>=1) {
            msum[pos] = msum[lson(pos)] + msum[rson(pos)];
            mmax[pos] = max(mmax[lson(pos)], mmax[rson(pos)]);
        }
    }
    void change(int pos, int val) { pos += M-1; msum[pos] = mmax[pos] = val; fix(pos); }
    int querymax(int s, int t) {
        int ans = -_oo;
        for(s=s+M-2,t=t+M;s^t^1;s>>=1,t>>=1) {
            if(~s & 1) ans = max(ans, mmax[s^1]);
            if( t & 1) ans = max(ans, mmax[t^1]);
        }
        return ans;
    }
    int querysum(int s, int t) {
        int ans = 0;
        for(s=s+M-2,t=t+M;s^t^1;s>>=1,t>>=1) {
            if(~s & 1) ans += msum[s^1];
            if( t & 1) ans += msum[t^1];
        }
        return ans;
    }
} ST;

int querymx(int s, int t) {
    int ans = -_oo;
    while(top[s] != top[t]) {
        if(dep[top[s]] < dep[top[t]]) swap(s, t);
        ans = max(ans, ST.querymax(tid[top[s]], tid[s]));
        s = fa[top[s]];
    }
    if(tid[s] > tid[t]) swap(s, t);
    ans = max(ans, ST.querymax(tid[s], tid[t]));
    return ans;
}

int querysum(int s, int t) {
    int ans = 0;
    while(top[s] != top[t]) {
        if(dep[top[s]] < dep[top[t]]) swap(s, t);
        ans += ST.querysum(tid[top[s]], tid[s]);
        s = fa[top[s]];
    }
    if(tid[s] > tid[t]) swap(s, t);
    ans += ST.querysum(tid[s], tid[t]);
    return ans;
}

void change(int v, int w) {
    ST.change(tid[v], w);
}

void work() {
    CLR(dep); CLR(siz); CLR(fa); CLR(son);
    CLR(top); CLR(tid); CLR(trank); tpos = 0;
    dfs1(1, 0, 0);
    dfs2(1, 1);
    ST.mkTree(N);

    char c[16]; int a, b; int t; scanf("%d", &t);
    while(t--) {
        scanf("%s", &c);
        switch(c[1]) {
        case 'M': { scanf("%d %d", &a, &b); printf("%d\n", querymx(a, b)); } break;
        case 'S': { scanf("%d %d", &a, &b); printf("%d\n", querysum(a, b)); } break;
        case 'H': { scanf("%d %d", &a, &b); change(a, b); }
        }
    }
}

int main() {
    scanf("%d", &N);
    CLR(POOL); CLR(Head); ppos = 0;
    input();
    work();
}