记录编号	39108	评测结果	AWWWWWWWWT
题目名称	危险游戏	最终得分	10
用户昵称	CC	是否通过	未通过
代码语言	C++	运行时间	1.102 s
提交时间	2012-07-04 17:49:02	内存使用	3.65 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 1000000000
using namespace std;
struct edge {
	int y,v;
	edge *next;
	edge (int y,int v,edge *next): y(y),v(v),next(next) {};
}*a[10050],*pre[10050];
struct bian {
	int x,y,v,index;
}c[100050],b[100050];
int n,m,tot,Q,T,ans;
int level[10050],fa[10050],fu[10050];
bool done[100050];
bool cmp(bian p,bian q) {
	return p.v < q.v;
}
int find(int x) {
	if (fa[x] == x) return x;
	else return fa[x] = find(fa[x]);
}
void KU() {
	sort(b + 1,b + T + 1,cmp);
	for (int i = 1;i <= n;i++) fa[i] = i;
	tot = 0;
	for (int i = 1;i <= T;i++) {
		int f1 = find(b[i].x),f2 = find(b[i].y);
		if (f1 == f2) continue;
		tot++;
		a[b[i].x] = new edge(b[i].y,b[i].v,a[b[i].x]);
		a[b[i].y] = new edge(b[i].x,b[i].v,a[b[i].y]);
		ans += b[i].v;
		fa[f1] = f2;
		done[b[i].index] = 1;
	}
}
void bfs() {
	memset(fu,0,sizeof(fu));
	memset(pre,0,sizeof(pre));
	memset(level,0,sizeof(level));
	int q[10050],head = 0,tail = 0;
	level[1] = 0;
	fu[1] = 1;
	q[0] = 1;
	while (head <= tail) {
		int now = q[head++];
		for (edge *p = a[now];p;p = p->next) 
			if (!fu[p->y]) {
				fu[q[++tail] = p->y] = now;
				pre[p->y] = p;
				level[p->y] = level[now] + 1;
			}
	}
}
	
void solve() {
	int u,t,maxl,tmp;
	scanf("%d", &Q);
	for (int i = 1;i <= Q;i++) {
		scanf("%d%d", &u, &t);
		c[u].v = t;
		if (done[u]) {
			for (edge *p = a[c[u].x];p;p = p->next) 
				if (p->y == c[u].y) {
					ans -= p->v;
					ans += t;
					p->v = t;
					printf("%d\n", ans);
					break;
				}
			for (edge *p = a[c[u].y];p;p = p->next)
				if (p->y == c[u].x) {
					p->v = t;
					break;
				}
			continue;
		} else {
			bfs();
			int p = c[u].x,q = c[u].y;
			if (level[p] > level[q]) std::swap(p,q);
			tmp = 0;
			while (level[q] != level[p]) {
				if (tmp < pre[q]->v) {
					tmp = pre[q]->v;
					maxl = q;
				}
				q = fu[q];
			}
			while (p != q) {
				if (tmp < pre[q]->v) {
					tmp = pre[q]->v;
					maxl = q;
				}
				if (tmp < pre[p]->v) {
					tmp = pre[p]->v;
					maxl = p;
				}
				p = fu[p];
				q = fu[q];
			}
			if (tmp < t) {
				printf("%d\n", ans);
				continue;
			} else {
				ans -= tmp;ans += t;
				int g = maxl,h = fu[maxl];
				if (a[h]->y == g) a[h] = a[h]->next;
				else for (edge *p = a[h];p;p = p->next) 
					if (p->next->y == g) {
						p->next = p->next->next;
						break;
					}
				if (a[g]->y == h) a[g] = a[g]->next;
				else for (edge *p = a[g];p;p = p->next) 
					if (p->next->y == h) {
						p->next = p->next->next;
						break;
					}
				a[c[u].x] = new edge(c[u].y,c[u].v,a[c[u].x]);
				a[c[u].y] = new edge(c[u].x,c[u].v,a[c[u].y]);
			}
		}
		printf("%d\n", ans);
	}
}
	
int main() {
	freopen("tubea.in","r",stdin);
	freopen("tubea.out","w",stdout);
	scanf("%d%d", &n, &T);
	for (int i = 1;i <= T;i++) {
		scanf("%d%d%d", &c[i].x, &c[i].y,&c[i].v);
		b[i] = c[i];
		b[i].index = i;
	}
	KU();
	printf("%d\n", ans);
	solve();
	return 0;
}