除草了。。
Crash的旅行计划
【问题描述】
过不了多久,Crash就要迎来他朝思暮想的暑假。在这个暑假里,他计划着到火星上旅游。在火星上有N个旅游景点,Crash用1至N这N个正整数对这些景点标号。旅游景点之间通过双向道路相连。由于火星的环境和地球有很大的差异,建立道路的成本也相对较高。为了节约成本,只有N-1条道路连接着这些旅游景点,不过可以保证任何两个不同的旅游景点都通过路径相连。
Crash预先在互联网上查阅了这些景点的信息,根据网上的介绍,他对每个景点都有一个印象值,这个印象值为一个整数。在这个旅行中,他会选择一个景点作为旅行的开始,并沿着存在的道路到达其他景点游玩。为了使旅行不显得乏味,Crash不会经过同一个景点超过一次。Crash还给这次旅行定义了一个快乐指数,也就是他经过的所有景点的印象值之和。
不过Crash是个奇怪的小朋友,他对于景点的印象值会发生改变,并且他也没有决定好应该从哪个景点开始旅行。因此他希望你能写一个程序帮他完成一个简单的任务:根据当前他对每个景点的印象值,计算从某个景点开始旅行所能获得的最大的快乐指数。
【输入格式】
输入的第一行包含一个字符和一个正整数N,字符为ABC中的一个,用来表示这个测试数据的类型(详见下面的数据规模和约定)。
第二行包含N个用空格隔开的整数,第i个整数表示Crash对i号景点的初始印象值。
接着有N-1行,每行两个正整数a、b(1 ≤a, b≤N),表示从a号景点到b号景点有一条无向道路相连。
最后是一些指令,指令只会是以下三种格式:
1.Change ux (1 ≤u≤N)将u号景点的印象值修改为x。
2.Query u (1 ≤u≤N) 询问从u号景点开始能获得的最大的快乐指数。
3.Done收到这个指令后,你的程序应该结束。
【输出格式】
对于每条Query指令,输出对应的最大快乐指数。
【样例输入1】
A 6
6 5 -4 3 -2 1
1 2
1 3
1 4
3 5
3 6
Query 3
Query 4
Change 6 10
Query 3
Change 2 -5
Query 3
Query 4
Done
【样例输出1】
7
14
7
6
15
【样例输入2】
B 5
5 -4 3 -2 1
1 2
2 3
3 4
4 5
Query 3
Change 5 10
Query 3
Query 2
Change 2 2
Query 3
Done
【样例输出2】
4
11
7
11
【数据规模和约定】
测试数据分为ABC三类,对于所有的测试数据都满足:在任何时候一个景点印象值的绝对值不超过10000,并且输入的道路一定能满足题目描述的要求,即使得任意两个不同的景点都能通过路径相连。
对于A类数据(占20%的分数)满足:N和指令的条数都不超过1000。
对于B类数据(占40%的分数)满足:N和指令的条数都不超过100000,且输入的第i条道路,连接着i号景点和i+1号景点(详见样例2)。
对于C类数据(占40%的分数)满足:N和指令的条数都不超过100000,且任何一个景点到1号景点需要通过的道路条数不超过40。
【特别说明】
由于数据大小限制为5MB,我只好对测试时的输入文件进行压缩处理。下面的函数可以将压缩的输入文件转化为原始输入文件。(函数从infile中读入压缩的输入文件,将解压缩后的输入文件输出到outfile中)
C/C++版本:
void Uncompress(FILE *infile, FILE *outfile) { int N, M, L, now, A, B, Q, tmp, i; char type = getc(infile); fscanf(infile, "%d%d%d", &N, &M, &L); fscanf(infile, "%d%d%d%d", &now, &A, &B, &Q); fprintf(outfile, "%c %d\n", type, N); for (i = 1; i <= N; i ++) { now = (now * A + B) % Q, tmp = now % 10000; now = (now * A + B) % Q; if (now * 2 < Q) tmp *= -1; if (i < N) fprintf(outfile, "%d ", tmp); else fprintf(outfile, "%d\n", tmp); } for (i = 1; i < N; i ++) { now = (now * A + B) % Q; tmp = (i < L) ? i : L; fprintf(outfile, "%d %d\n", i - now % tmp, i + 1); } for (i = 1; i < M; i ++) { now = (now * A + B) % Q; if (now * 3 < Q) { now = (now * A + B) % Q; fprintf(outfile, "Query %d\n", now % N + 1); } else { now = (now * A + B) % Q, tmp = now % 10000; now = (now * A + B) % Q; if (now * 2 < Q) tmp *= -1; now = (now * A + B) % Q; fprintf(outfile, "Change %d %d\n", now % N + 1, tmp); } } fprintf(outfile, "Done\n"); } |
Pascal版本:
procedure Uncompress(varinfile, outfile : text); var N, M, L, now, A, B, Q, tmp, i : longint; ch : char; begin read(infile, ch, N, M, L, now, A, B, Q); writeln(outfile, ch, ' ', N); for i := 1 to N do begin now := (now * A + B) mod Q; tmp := now mod 10000; now := (now * A + B) mod Q; if now * 2 < Q then tmp := -tmp; if i < n then write(outfile, tmp, ' ') else writeln(outfile, tmp); end; for i := 1 to N - 1 do begin now := (now * A + B) mod Q; if i < L then tmp := i else tmp := L; writeln(outfile, i - now mod tmp, ' ', i + 1); end; for i := 1 to M - 1 do begin now := (now * A + B) mod Q; if now * 3 < Q then begin now := (now * A + B) mod Q; writeln(outfile, 'Query ', now mod N + 1); end else begin now := (now * A + B) mod Q; tmp := now mod 10000; now := (now * A + B) mod Q; if now * 2 < Q then tmp := -tmp; now := (now * A + B) mod Q; writeln(outfile, 'Change ', now mod N + 1, ' ', tmp); end; end; writeln(outfile, 'Done'); end; |
下面给出一个具体的例子。travel_compressed.in表示压缩的输入文件,travel.in表示解压缩后的输入文件。
travel_compressed.in |
travel.in |
A 5 7 3 17627 543 14278 380043 |
A 5 -4664 7653 -3584 -210 5852 1 2 1 3 2 4 3 5 Change 5 -3724 Query 4 Change 3 -5628 Query 2 Change 5 569 Query 5 Done |
mycode:
/** * Problem:travel * Author:Shun Yao * Time:2013.8.23 * Result:Accepted * Memo:Segment-Tree, DFS */ #include <cstring> #include <cstdio> #include <climits> #define MAXN 100010 long a[MAXN]; class Edge { public: long v; Edge *next; Edge() {} ~Edge() {} Edge(long V, Edge *ne) : v(V), next(ne) {} } *g[MAXN]; void add(long x, long y) { g[x] = new Edge(y, g[x]); g[y] = new Edge(x, g[y]); } long min(long x, long y) { return x < y ? x : y; } long max(long x, long y) { return x > y ? x : y; } class SegT { public: long v, ma, mi; SegT *l, *r; SegT() {} ~SegT() {} } *root; void build(SegT *&p, long l, long r) { p = new SegT(); p->v = 0; if (l == r) p->ma = p->mi = a[l]; else { build(p->l, l, (l + r) >> 1); build(p->r, ((l + r) >> 1) + 1, r); p->ma = max(p->l->ma, p->r->ma); p->mi = min(p->l->mi, p->r->mi); } } long query(SegT *&p, long l, long r, long x) { if (l == r) return p->ma; if (p->v) { p->l->v += p->v; p->l->ma += p->v; p->l->mi += p->v; p->r->v += p->v; p->r->ma += p->v; p->r->mi += p->v; p->v = 0; } if (x <= ((l + r) >> 1)) return query(p->l, l, (l + r) >> 1, x); else return query(p->r, ((l + r) >> 1) + 1, r, x); } long queryma(SegT *&p, long l, long r, long L, long R) { if (l == L && r == R) return p->ma; if (p->v) { p->l->v += p->v; p->l->ma += p->v; p->l->mi += p->v; p->r->v += p->v; p->r->ma += p->v; p->r->mi += p->v; p->v = 0; } if (R <= ((l + r) >> 1)) return queryma(p->l, l, (l + r) >> 1, L, R); else if (L > ((l + r) >> 1)) return queryma(p->r, ((l + r) >> 1) + 1, r, L, R); return max(queryma(p->l, l, (l + r) >> 1, L, (l + r) >> 1), queryma(p->r, ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, R)); } long querymi(SegT *&p, long l, long r, long L, long R) { if (l == L && r == R) return p->mi; if (p->v) { p->l->v += p->v; p->l->ma += p->v; p->l->mi += p->v; p->r->v += p->v; p->r->ma += p->v; p->r->mi += p->v; p->v = 0; } if (R <= ((l + r) >> 1)) return querymi(p->l, l, (l + r) >> 1, L, R); else if (L > ((l + r) >> 1)) return querymi(p->r, ((l + r) >> 1) + 1, r, L, R); return min(querymi(p->l, l, (l + r) >> 1, L, (l + r) >> 1), querymi(p->r, ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, R)); } void modify(SegT *&p, long l, long r, long L, long R, long v) { if (r < L || R < l) return; if (l >= L && r <= R) { p->v += v; p->ma += v; p->mi += v; return; } if (p->v) { p->l->v += p->v; p->l->ma += p->v; p->l->mi += p->v; p->r->v += p->v; p->r->ma += p->v; p->r->mi += p->v; p->v = 0; } modify(p->l, l, (l + r) >> 1, L, R, v); modify(p->r, ((l + r) >> 1) + 1, r, L, R, v); p->ma = max(p->l->ma, p->r->ma); p->mi = min(p->l->mi, p->r->mi); } long tot = -1, t[MAXN], b[MAXN], dfn[MAXN], dff[MAXN], fa[MAXN]; void dfs(long x) { dfn[x] = ++tot; t[tot] = x; for (Edge *e = g[x]; e; e = e->next) if (e->v != fa[x]) { a[e->v] += a[x]; fa[e->v] = x; dfs(e->v); } dff[x] = tot; } void Uncompress(FILE *infile) { long N, M, L, now, A, B, Q, tmp, i, j, k, ans; char type = getc(infile); fscanf(infile, "%ld%ld%ld", &N, &M, &L); fscanf(infile, "%ld%ld%ld%ld", &now, &A, &B, &Q); for (i = 1; i <= N; i ++) { now = (now * A + B) % Q, tmp = now % 10000; now = (now * A + B) % Q; if (now * 2 < Q) tmp *= -1; a[i] = tmp; } for (i = 1; i < N; i ++) { now = (now * A + B) % Q; tmp = (i < L) ? i : L; if (type != 'B') add(i - now % tmp, i + 1); } switch (type) { case 'A': memset(fa, 0, sizeof fa); fa[0] = -1; add(0, 1); dfs(0); a[0] = 0; for (i = 0; i <= N; ++i) b[i] = a[t[i]]; memcpy(a, b, sizeof a); build(root, 0, N); break; case 'B': a[0] = 0; for (i = 1; i <= N; ++i) a[i] += a[i - 1]; build(root, 0, N); break; case 'C': memset(fa, 0, sizeof fa); fa[0] = -1; add(0, 1); dfs(0); a[0] = 0; for (i = 1; i <= N; ++i) b[i] = a[t[i]]; memcpy(a, b, sizeof a); build(root, 0, N); break; } for (i = 1; i < M; i ++) { now = (now * A + B) % Q; if (now * 3 < Q) { now = (now * A + B) % Q; k = now % N + 1; switch (type) { case 'A': ans = queryma(root, 0, N, dfn[k], dff[k]) - query(root, 0, N, dfn[fa[k]]); j = query(root, 0, N, dfn[k]); while (k > 1) { tmp = INT_MIN; if (dfn[fa[k]] <= dfn[k] - 1) tmp = max(tmp, queryma(root, 0, N, dfn[fa[k]], dfn[k] - 1)); if (dff[k] + 1 <= dff[fa[k]]) tmp = max(tmp, queryma(root, 0, N, dff[k] + 1, dff[fa[k]])); ans = max(ans, tmp + j - query(root, 0, N, dfn[fa[fa[k]]]) - query(root, 0, N, dfn[fa[k]])); k = fa[k]; } printf("%ld\n", ans); break; case 'B': ans = query(root, 0, N, k) - querymi(root, 0, N, 0, k - 1); if (k != N) ans = max(ans, queryma(root, 0, N, k + 1, N) - query(root, 0, N, k - 1)); printf("%ld\n", ans); break; case 'C': ans = queryma(root, 0, N, dfn[k], dff[k]) - query(root, 0, N, dfn[fa[k]]); j = query(root, 0, N, dfn[k]); while (k > 1) { tmp = INT_MIN; if (dfn[fa[k]] <= dfn[k] - 1) tmp = max(tmp, queryma(root, 0, N, dfn[fa[k]], dfn[k] - 1)); if (dff[k] + 1 <= dff[fa[k]]) tmp = max(tmp, queryma(root, 0, N, dff[k] + 1, dff[fa[k]])); ans = max(ans, tmp + j - query(root, 0, N, dfn[fa[fa[k]]]) - query(root, 0, N, dfn[fa[k]])); k = fa[k]; } printf("%ld\n", ans); break; } } else { now = (now * A + B) % Q, tmp = now % 10000; now = (now * A + B) % Q; if (now * 2 < Q) tmp *= -1; now = (now * A + B) % Q; k = now % N + 1; switch (type) { case 'A': j = query(root, 0, N, dfn[k]) - query(root, 0, N, dfn[fa[k]]); modify(root, 0, N, dfn[k], dff[k], tmp - j); break; case 'B': j = query(root, 0, N, k) - query(root, 0, N, k - 1); modify(root, 0, N, k, N, tmp - j); break; case 'C': j = query(root, 0, N, dfn[k]) - query(root, 0, N, dfn[fa[k]]); modify(root, 0, N, dfn[k], dff[k], tmp - j); break; } } } } int main() { freopen("travel.in", "r", stdin); freopen("travel.out", "w", stdout); Uncompress(stdin); fclose(stdin); fclose(stdout); return 0; }