LCA+RMQ。挺不错的一道题目。
思路是如何通过LCA维护费用。当加入新的点u是，费用增量为
dis[u]-dis[lca(u, lower_u)] - dis[lca(u, greater_u)] + dis[lca(lower_u, greater_u)]。
若beg[u]大于当前最大值或小于最小值，lower_u=min of current, greater_u = max of current。
1 /* 5296 */ 2 #include <iostream> 3 #include <sstream> 4 #include <string> 5 #include <map> 6 #include <queue> 7 #include <set> 8 #include <stack> 9 #include <vector> 10 #include <deque> 11 #include <algorithm> 12 #include <cstdio> 13 #include <cmath> 14 #include <ctime> 15 #include <cstring> 16 #include <climits> 17 #include <cctype> 18 #include <cassert> 19 #include <functional> 20 #include <iterator> 21 #include <iomanip> 22 using namespace std; 23 //#pragma comment(linker,"/STACK:102400000,1024000") 24 25 #define sti set<int> 26 #define stpii set<pair<int, int> > 27 #define mpii map<int,int> 28 #define vi vector<int> 29 #define pii pair<int,int> 30 #define vpii vector<pair<int,int> > 31 #define rep(i, a, n) for (int i=a;i<n;++i) 32 #define per(i, a, n) for (int i=n-1;i>=a;--i) 33 #define clr clear 34 #define pb push_back 35 #define mp make_pair 36 #define fir first 37 #define sec second 38 #define all(x) (x).begin(),(x).end() 39 #define SZ(x) ((int)(x).size()) 40 #define lson l, mid, rt<<1 41 #define rson mid+1, r, rt<<1|1 42 43 typedef struct { 44 int v, w, nxt; 45 } edge_t; 46 47 const int maxn = 1e5+5; 48 const int maxv = maxn; 49 const int maxe = maxv * 2; 50 int head[maxv]; 51 edge_t E[maxe]; 52 int dis[maxn], deep[maxn]; 53 bool visit[maxn]; 54 int beg[maxn]; 55 int V[maxn<<1], D[maxn<<1]; 56 int dp[18][maxn<<1]; 57 int l, top; 58 sti st; 59 sti::iterator iter; 60 61 void init() { 62 st.clr(); 63 memset(visit, false, sizeof(visit)); 64 memset(head, -1, sizeof(head)); 65 l = top = 0; 66 } 67 68 void addEdge(int u, int v, int w) { 69 E[l].v = v; 70 E[l].w = w; 71 E[l].nxt = head[u]; 72 head[u] = l++; 73 74 E[l].v = u; 75 E[l].w = w; 76 E[l].nxt = head[v]; 77 head[v] = l++; 78 } 79 80 void dfs(int u, int fa, int d, int w) { 81 dis[u] = w; 82 V[++top] = u; 83 D[top] = d; 84 beg[u] = top; 85 86 int v, k; 87 88 for (k=head[u]; k!=-1; k=E[k].nxt) { 89 v = E[k].v; 90 if (v == fa) 91 continue; 92 dfs(v, u, d+1, w+E[k].w); 93 V[++top] = u; 94 D[top] = d; 95 } 96 } 97 98 void init_RMQ(int n) { 99 int i, j; 100 101 for (i=1; i<=n; ++i) 102 dp[0][i] = i; 103 for (j=1; (1<<j)<=n; ++j) 104 for (i=1; i+(1<<j)-1<=n; ++i) 105 if (D[dp[j-1][i]] < D[dp[j-1][i+(1<<(j-1))]]) 106 dp[j][i] = dp[j-1][i]; 107 else 108 dp[j][i] = dp[j-1][i+(1<<(j-1))]; 109 } 110 111 int RMQ(int l, int r) { 112 if (l > r) 113 swap(l, r); 114 115 int k = 0; 116 117 while (1<<(k+1) <= r-l+1) 118 ++k; 119 120 if (D[dp[k][l]] < D[dp[k][r-(1<<k)+1]]) 121 return V[dp[k][l]]; 122 else 123 return V[dp[k][r-(1<<k)+1]]; 124 } 125 126 int calc(int u) { 127 if (st.empty()) 128 return 0; 129 130 int x, y; 131 132 iter = st.upper_bound(beg[u]); 133 if (iter == st.end() || iter==st.begin()) { 134 y = *st.rbegin(); 135 x = *st.begin(); 136 } else { 137 y = *iter; 138 --iter; 139 x = *iter; 140 } 141 142 int ret = 0; 143 144 ret = dis[u] - dis[RMQ(x, beg[u])] - dis[RMQ(beg[u], y)] + dis[RMQ(x, y)]; 145 return ret; 146 } 147 148 int main() { 149 ios::sync_with_stdio(false); 150 #ifndef ONLINE_JUDGE 151 freopen("data.in", "r", stdin); 152 freopen("data.out", "w", stdout); 153 #endif 154 155 int t; 156 int n, q; 157 int u, v, w; 158 int op; 159 int ans; 160 161 scanf("%d", &t); 162 rep(tt, 1, t+1) { 163 scanf("%d %d", &n, &q); 164 init(); 165 rep(i, 1, n) { 166 scanf("%d %d %d", &u, &v, &w); 167 addEdge(u, v, w); 168 } 169 dfs(1, 0, 0, 0); 170 init_RMQ(top); 171 printf("Case #%d: ", tt); 172 ans = 0; 173 while (q--) { 174 scanf("%d %d", &op, &u); 175 if (op == 1) { 176 if (!visit[u]) { 177 visit[u] = true; 178 ans += calc(u); 179 st.insert(beg[u]); 180 } 181 } else { 182 if (visit[u]) { 183 visit[u] = false; 184 st.erase(beg[u]); 185 ans -= calc(u); 186 } 187 } 188 printf("%d ", ans); 189 } 190 } 191 192 #ifndef ONLINE_JUDGE 193 printf("time = %d. ", (int)clock()); 194 #endif 195 196 return 0; 197 }
数据发生器。
1 from random import randint, shuffle 2 import shutil 3 import string 4 5 6 def GenDataIn(): 7 with open("data.in", "w") as fout: 8 t = 10 9 bound = 10**3 10 fout.write("%d " % (t)) 11 for tt in xrange(t): 12 n = randint(20, 30) 13 q = randint(20, 30) 14 fout.write("%d %d " % (n, q)) 15 ust = [1] 16 vst = range(1, n+1) 17 ust.append(1) 18 vst.remove(1) 19 un = 1 20 vn = n - 1 21 for i in xrange(1, n): 22 uidx = randint(0, un-1) 23 u = ust[uidx] 24 vidx = randint(0, vn-1) 25 v = vst[vidx] 26 ust.append(v) 27 vst.remove(v) 28 un += 1 29 vn -= 1 30 w = randint(1, 100) 31 fout.write("%d %d %d " % (u, v, w)) 32 L = [] 33 for i in xrange(q): 34 op = randint(1, 2) 35 x = randint(1, n) 36 fout.write("%d %d " % (op, x)) 37 38 39 40 def MovDataIn(): 41 desFileName = "F:eclipse_prjworkspacehdojdata.in" 42 shutil.copyfile("data.in", desFileName) 43 44 45 if __name__ == "__main__": 46 GenDataIn() 47 MovDataIn()