C++11(clang++ 3.9) 解法, 执行用时: 988ms, 内存消耗: 125444K, 提交时间: 2020-10-14 12:09:04

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N=4e5+5;
int n,m,q,x[N],y[N],z[N],bit[N],ans[N];
vector<pair<pair<int,int>,int> >Q[N];
struct Kruskal_Rebuild_Tree{
	int tot,dsu[N],fa[19][N],ch[2][N],val[N],dfn[N],low[N],id[N],cnt;
	void init(){
		for(int i=1;i<=n;++i)
			dsu[i]=i,val[i]=1e9;
		tot=n;
	}
	int find(int x){
		return x==dsu[x]?x:dsu[x]=find(dsu[x]);
	}
	void link(int x,int y,int z){
		x=find(x);y=find(y);
		if(x==y)return;
		++tot;
		dsu[tot]=dsu[x]=dsu[y]=tot;
		fa[0][x]=fa[0][y]=tot;
		ch[0][tot]=x;ch[1][tot]=y;
		val[tot]=z;
	}
	void dfs(int u){
		dfn[u]=cnt+1;
		if(u<=n)id[++cnt]=u;
		if(ch[0][u])dfs(ch[0][u]);
		if(ch[1][u])dfs(ch[1][u]);
		low[u]=cnt;
	}
	void build(){
		for(int j=1;j<19;++j)
			for(int i=1;i<=tot;++i)
				fa[j][i]=fa[j-1][fa[j-1][i]];
		for(int i=tot;i;--i)
			if(!dfn[i])
				dfs(i);
	}
	pair<int,int>query(int x,int t){
		for(int j=18;~j;--j)
			if(fa[j][x]&&val[fa[j][x]]<=t)
				x=fa[j][x];
		return make_pair(dfn[x],low[x]);
	}
}T0,T1;
void modify(int x){
	while(x<=T1.tot)
		++bit[x],x+=x&-x;
}
int query(int x){
	int res=0;
	while(x)
		res+=bit[x],x^=x&-x;
	return res;
}
int main(){
	n=gi();m=gi();q=gi();
	T0.init();T1.init();
	for(int i=1;i<=m;++i)
		x[i]=gi()+1,y[i]=gi()+1,z[i]=gi();
	for(int i=1;i<=m;++i)
		if(!z[i])
			T0.link(x[i],y[i],i);
	for(int i=m;i;--i)
		if(z[i])
			T1.link(x[i],y[i],-i);
	T0.build();T1.build();
	for(int i=1;i<=q;++i){
		int x=gi()+1,t=gi();
		pair<int,int>p0=T0.query(x,t),p1=T1.query(x,-t);
		Q[p0.first-1].push_back(make_pair(p1,-i));
		Q[p0.second].push_back(make_pair(p1,i));
	}
	for(int i=1;i<=n;++i){
		modify(T1.dfn[T0.id[i]]);
		for(auto p:Q[i]){
			int res=query(p.first.second)-query(p.first.first-1);
			if(p.second>0)
				ans[p.second]+=res;
			else
				ans[-p.second]-=res;
		}
	}
	for(int i=1;i<=q;++i)
		printf("%d\n",ans[i]);
	return 0;
}