[动态图]

给一个图，每一条边有一个消失的时刻，询问1~K每个时刻两两可达的点对有多少对？

题目链接:http://poj.openjudge.cn/practice/C15C/

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define maxn 200010

using namespace std;
typedef long long ll;

ll ans;
int N, M, K;
int h[maxn], cnt;
struct Edge{int u, v, nxt;}edge[maxn];
void add(int x, int u, int v){
	edge[++ cnt] = (Edge){u, v, h[x]};
	h[x] = cnt;
}

void init(){
	memset(h, 0, sizeof h);
	ans = cnt = 0;
}

struct Node{
	int u, v, cntu, cntv, ranku, rankv;
	Node(int u = 0, int v = 0, int cntu = 0, int cntv = 0, int ranku = 0, int rankv = 0):
		u(u), v(v), cntu(cntu), cntv(cntv), ranku(ranku), rankv(rankv){}
}st[maxn];

int top;

namespace Set{
	int rank[maxn], fa[maxn], c[maxn];
	
	void Init(){
		for(int i = 1; i <= N; i ++)
		    c[i] = 1, fa[i] = i, rank[i] = 1;
	}
	
	int Findroot(int x){
		while(x != fa[x])x = fa[x];
		return x;
	}
	
	void Union(int u, int v){
        u = Findroot(u);
		v = Findroot(v);
		if(u == v)return;
		ans += (ll)c[u] * c[v];
		st[++ top] = (Node){u, v, c[u], c[v], rank[u], rank[v]};
        if(rank[u] == rank[v]){
			if(c[u] < c[v])swap(u, v);
			fa[v] = u;
			c[u] += c[v];
			rank[u] = rank[v] + 1;
			return;
		}
		if(rank[u] < rank[v])swap(u, v);
		fa[v] = u;
		c[u] += c[v];
	}
	
	int Pushback(int rtop){
		for(; top > rtop; top --){
			int u = st[top].u, v = st[top].v;
			ans -= (ll)st[top].cntu * st[top].cntv;
			fa[u] = u, fa[v] = v;
			c[u] = st[top].cntu;
			c[v] = st[top].cntv;
			rank[u] = st[top].ranku;
			rank[v] = st[top].rankv;
		}
	}
}

void cdq(int l, int r){
	if(l == r){
		printf("%lld
", ans);
		return;
	}
	int mid = l + r >> 1, rtop = top;
	for(int i = mid + 1; i <= r; i ++)
	    for(int j = h[i]; j; j = edge[j].nxt)
			Set::Union(edge[j].u, edge[j].v);
	cdq(l, mid);
	Set::Pushback(rtop);
	for(int i = l; i <= mid; i ++)
	    for(int j = h[i]; j; j = edge[j].nxt)
	        Set::Union(edge[j].u, edge[j].v);
	cdq(mid + 1, r);
	Set::Pushback(rtop);
}

void solve(){
	init();
	int u, v, c;
	Set::Init();
	for(int i = 1; i <= M; i ++){
		scanf("%d%d%d", &u, &v, &c);
		add(c, u, v);
	}
	cdq(1, K);
}

int main(){
	while(~scanf("%d%d%d", &N, &M, &K))
	    solve();
	return 0;
}