[洛谷P4185] [USACO18JAN]MooTube

题目链接：###

题意：###

给定一颗N个节点的树，定义两点距离为他们之间路径中边权最小值。

Q次询问K,V，询问到V距离>=K的点有多少（不含V）

呃呃呃呃考试的时候直奔了T3，结果公式推挂了（。。）最后5min回来搞T1，看出了正解然而手速跟不上……

分析：###

把所有的询问先离线下来存在一个结构体里并记录顺序（以便输出），然后分别把边和询问按w和k从大到小排序

用一个循环扫询问，每次询问把大于等于ask[i].k的边加进并查集并更新总和，最后按顺序排回来输出

具体的操作都在代码里

代码：###

#include<bits/stdc++.h>

#define N (200000+5)

using namespace std;

inline int read(){

	int cnt=0,f=1;char c;

	c=getchar();

	while(!isdigit(c)){

		if(c=='-')f=-f;

		c=getchar();

	}

	while(isdigit(c)){

		cnt=cnt*10+c-'0';

		c=getchar();

	}

	return cnt*f;

}

int n,q,id[N],p=1,fa[N];

struct node{int x;int y;int w;} edge[N];

struct node2{int num;int v;int k;int res;} ask[N];

bool cmp(node a,node b){

	return a.w>b.w;

}

bool cmp2(node2 a,node2 b){

	return a.k>b.k;

}

bool cmp3(node2 a,node2 b){

	return a.num<b.num;

}

int get_father(int x){

	if(fa[x]==x)return x;

	return fa[x]=get_father(fa[x]);

}

void merge(int a,int b){

	int x=get_father(a);

	int y=get_father(b);

	if(x==y) return;

	else fa[x]=y;

	id[y]+=id[x];

}

int main(){

	n=read();q=read();

	for(register int i=1;i<=n;i++) fa[i]=i,id[i]=1;

	for(register int i=1;i<n;i++) {

		edge[i].x=read();

		edge[i].y=read();

		edge[i].w=read();

	}

	for(register int i=1;i<=q;i++) {

		ask[i].k=read();

		ask[i].v=read();

		ask[i].num=i;

	}

	sort(edge+1,edge+n,cmp);

	sort(ask+1,ask+q+1,cmp2);

	for(register int i=1;i<=q;i++){

		while(edge[p].w>=ask[i].k&&p<n){

			merge(edge[p].x,edge[p].y);

			p++;

		}

		int t=get_father(ask[i].v);

		ask[i].res=id[t]-1;

	}

	sort(ask+1,ask+q+1,cmp3);

	for(register int i=1;i<=q;i++) printf("%d\n",ask[i].res);

	return 0;

}

巴特西

[洛谷P4185] [USACO18JAN]MooTube

题目链接：###

题意：###

分析：###

代码：###

最新文章

热门文章