首页 > 其他分享 >P4185 [USACO18JAN] MooTube G 题解

P4185 [USACO18JAN] MooTube G 题解

时间:2024-09-18 16:25:50浏览次数:14  
标签:USACO18JAN 连通 int 题解 查集 100005 MooTube Quest

水一篇题解。
也是一道并查集的好题,涉及另一个并查集的基本应用,并查集维护连通块(我跟并查集过不去了???)
大致题意:
给你一棵树,对于每次询问求一个点所在连通块中到达该点的最小路径权值大于给定值的点个数。

既然都连通块了,那我们在维护连通块的时候直接不把权值大于K的边加进去,用并查集维护,按秩合并,答案就是连通块大小减一。
但是考虑对于每次询问都重新操作显然是不行的,所以离线下来按K排序。
Code:

#include<bits/stdc++.h>
using namespace std;
int n,q,fa[100005],siz[100005],x,y;
struct Edge{
    int u,v,val;
}edge[100005];
struct Quest{
    int k,wh,id,ans;
}quest[100005];
bool cmp(Edge a,Edge b){
    return a.val>b.val;
}
bool cmpq(Quest a,Quest b){
    return a.k>b.k;
}
bool cmqp(Quest a,Quest b){
    return a.id<b.id;
}
int find(int x){
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
int main(){
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n-1;++i) scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].val);
    for(int i=1;i<=q;++i) scanf("%d %d",&quest[i].k,&quest[i].wh),quest[i].id=i;
    sort(edge+1,edge+n,cmp);
    sort(quest+1,quest+q+1,cmpq);
    for(int i=1;i<=n;++i) siz[i]=1,fa[i]=i;
    int j=1;
    for(int i=1;i<=q;++i){
        for(j;edge[j].val>=quest[i].k&&j<n;++j){
        	x=find(edge[j].u),y=find(edge[j].v);
            if(x!=y){
            	fa[x]=y;
            	siz[y]+=siz[x];
			} 
        }
        quest[i].ans=siz[find(quest[i].wh)]-1;
    }
    sort(quest+1,quest+q+1,cmqp);
    for(int i=1;i<=q;++i) printf("%d\n",quest[i].ans);
    return 0;
}

标签:USACO18JAN,连通,int,题解,查集,100005,MooTube,Quest
From: https://www.cnblogs.com/mountzhu/p/18418776

相关文章

  • CF1716C Robot in a Hallway 题解
    容易发现合法路径一定形如:先弯弯曲曲地走(即向下、向右、向上、向右地移动),再直接向右走到头,碰到边界后折回来。所以考虑枚举弯曲地走的部分,这部分的最快时间容易求出。只需考虑快速求出剩余部分的最快时间,设对于第\(i\)第\(j\)列,这个时间为\(f_{i,j}\)。发现移动和等待格子......
  • 洛谷P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫 题解 期望DP
    题目链接:https://www.luogu.com.cn/problem/P8774思路:设\(f_i\)为甲壳虫从高度\(i\)到达高度\(n\)因为从高度\(i\)走\(1\)步有\(1-P_{i+1}\)的概率到达高度\(i+1\),有\(P_{i+1}\)的概率到达高度\(0\),所以:\(f_i=1+(1-P_{i+1})\timesf_{i+1}+P_{i+1}\times......
  • 洛谷P4550 收集邮票 题解 期望DP
    题目链接:https://www.luogu.com.cn/problem/P4550解题思路:定义状态\(f_i\)表示目前已经取到\(i\)种邮票的情况下,取完所有\(n\)很明显,\(f_n=0\),因为此时已经取完了\(n\)如果当前已经取到了\(i\)有\(\frac{i}{n}\)的概率取到现有的邮票(此时仍然拥有\(i\)有\(1-\frac{i......
  • P11072 Alice and Bob 题解
    简单博弈题。先说结论,如果存在\(a_i=0\)使得\(1\lei\lea_1\)的话,那么先手必胜,否则后手必胜。若满足上述条件显然先手必胜,将\(0\)搞到第一个就行。否则Alice每操作一次,如果操作后满足了上述条件,那么Bob赢,否则Bob只要不动就行。但是下一轮Alice必须动,要不然两......
  • 【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)
    [NOIP2005普及组]采药题目描述辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株......
  • 历年CSP-J初赛真题解析 | 2019年CSP-J初赛阅读程序(16-33)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客#include<cstdio>#include<cstring>usingnamespacestd;charst[100];intmain(){scanf("%s",st);intn......