题解 P4185 【[USACO18JAN]MooTube】

哇没想到我也能做提高+的题好开心 一开始很简单粗暴地想到了邻接矩阵，做到10分才发觉这么高大上的题目你用这个方法来做是不是大傻X 看了大牛 elijahqi 的题解就想明白了原来是并查集啊~~哈哈哈~~ 蒟蒻的第一篇题解就你了哈哈 思路： 1. 在并查集的基础上加一点料，并查集原来是有边就把它连的两个点合并嘛，在这里我们吧、加一个条件，要>=k即符合条件的边才给它合并，这样的话这个连通块中所有的点都符合条件啦 2. 但是如果每次询问都重新合并一次的话会超时啊孩纸，所以我们用到两个快排，把每条边从大到小排 ，再把 询问的k从大到小排，先做最大的k，把符合条件的点合并后（不要忘记统计结点数，这个才是我们想要的嘛），那么下一个k肯定比这个小啦（排序了嘛），那么符合大k的点肯定符合小k的点啦，那么就不用再重复合并啦，做到第i个k，这个连通块中的结点就符合条件啦 ~~阿拉拉拉~~ emmm好像就这些把，我能理解的想必大神们都能理解嘻嘻 如果我说得有什么不对或遗漏的欢迎评论哦 不BB了上题解 ```cpp #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int j=1,n,q,number[110000],father[110000],ans[110000]; struct kind{ int start; int end; int w; }bian[110000]; struct kind2 { int k; int v; int id; }ask[110000]; int cmp(kind x,kind y){ return x.w>y.w; } int cmp2(kind2 x,kind2 y){ return x.k>y.k; } int getfather(int x) //寻找x的父节点 { if (father[x]!=x) father[x]=getfather(father[x]); return father[x]; } void onion(int x,int y) { x=getfather(x); y=getfather(y); if (x!=y) { father[x]=y; //合并父节点就把它们合并啦啦啦 number[y]+=number[x]; //父亲又多了几个儿子哈哈 } } int main() { cin>>n>>q; for (int i=1;i<=n;i++) { father[i]=i; number[i]=1; //number[]统计连通块中的结点数量 } for (int i=1;i<n;i++) cin>>bian[i].start>>bian[i].end>>bian[i].w; //读入起始点，到达点，边（连自己都觉得幼稚的数组bian[]） for (int i=1;i<=q;i++) { cin>>ask[i].k>>ask[i].v; ask[i].id=i; } //“离线”操作 ，因为后面还要对询问中的k进行排序（“离线”是指读入完后再操作，“在线”是指边读入边操作） sort(bian+1,bian+n+1,cmp); //对bian[]数组进行快排，把每条边的长度从大到小排，方便后面将>=k的边连接的点进行合并 sort(ask+1,ask+1+q,cmp2); //对ask[]询问数组进行快排，把询问的k从大到小排， for (int i=1;i<=q;i++) //对每个个询问进行操作 { while (j<n&&bian[j].w>=ask[i].k) //也可以用for语句代替，不过要把bian[j].w>=ask[i].k写在 for()括号里，避免多余的操作，不然会TLE的啊 //把每条>=k的边连接的点进行合并，即将符合条件的点都拉进这个连通块，那么这个连通块中所有的点都符合条件 //注意：变量j的声明一定要放在外面啊，不然会TLE，为什么呢，因为我们是把k从大做到小，k=4这个连通块里的结点肯定也符合k=3的这个条件，所以就不必要做重复的结合啦 { onion(bian[j].start,bian[j].end); j++; } ans[ask[i].id]=number[getfather(ask[i].v)]; //ans[]就是要输出的东西啦，要保证原来的输入对应输出，就需要ans[ask.id]这个东西，找到v点的父节点，那么符合条件的节点数就在number[]里面啦啦啦 } for (int i=1;i<=q;i++) cout<<ans[i]-1<<endl; //去掉自己一个结点后输出 return 0; //Yeah~~ } ```