Codeforces Round #582 (Div. 3) G. Path Queries (并查集计数)

题意:给你带边权的树,有\(m\)次询问,每次询问有多少点对\((u,v)\)之间简单路径上的最大边权不超过\(q_i\).

题解:真的想不到用最小生成树来写啊....

我们对边权排序,然后再对询问的\(q_i\)排序,我们可以枚举\(q_i\),然后从last开始遍历边权,如果边权不大于\(q_i\),那么就可以用并查集将两个连通块合并且计数(因为我们是从小到大枚举的,所以将它们合并并不会对后面有影响,反而还会方便我们计数),\(cnt\)表示连通块的节点数,合并时贡献为\(res=cnt[fu]*cnt[fv]\).

代码:

#define int long long

struct misaka{

	int u,v,w;

	bool operator < (const misaka & mikoto) const{

		return w<mikoto.w;

	}

}e[N];

struct query{

	int w;

	int id;

	bool operator < (const query & mikoto) const {

		return w<mikoto.w;

	}

}q[N];

int n,m;

int p[N];

int cnt[N];

int ans[N];

int res;

int find(int x){

	if(p[x]!=x) p[x]=find(p[x]);

	return p[x];

}

signed main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>n>>m;

	rep(i,1,n-1){

		cin>>e[i].u>>e[i].v>>e[i].w;

	}

	rep(i,1,n){

		p[i]=i;

		cnt[i]=1;

	}

	rep(i,1,m){

		cin>>q[i].w;

		q[i].id=i;

	}

	sort(e+1,e+n);

	sort(q+1,q+1+m);

	int last=1;

	rep(i,1,m){

		rep(j,last,n-1){

			if(e[j].w<=q[i].w){

				int u=e[j].u;

				int v=e[j].v;

				int fu=find(u);

				int fv=find(v);

				if(fu==fv) continue;

				res+=cnt[fv]*cnt[fu];

				cnt[fv]+=cnt[fu];

				cnt[fu]=0;

				p[fu]=fv;

				last++;

			}

			else break;

		}

		ans[q[i].id]=res;

	}

	rep(i,1,m) cout<<ans[i]<<' ';

    return 0;

}

Codeforces Round #582 (Div. 3) G. Path Queries (并查集计数)的相关教程结束。