离线+生成树+并查集——cf1213G

悠悠 2023-10-11 09:09 62阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    #define N 200005
    #define ll long long 
    struct Edge{
        int u,v,w;}e[N];
    struct Query{
        int id,qq;}qq[N];
    int n,q;
    ll ans[N],sum;
    bool operator<(Edge a,Edge b){
        return a.w<b.w;}
    bool operator<(Query a,Query b){
        return a.qq<b.qq;}
    
    int F[N],size[N];
    int find(int x){
        if(F[x]==x)return x;
        int f=find(F[x]);
        return F[x]=f;
    }
    void bing(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1==f2)return;
        sum-=(ll)size[f1]*(size[f1]-1)/2;
        sum-=(ll)size[f2]*(size[f2]-1)/2;
        size[f1]+=size[f2];
        sum+=(ll)size[f1]*(size[f1]-1)/2;
        F[f2]=f1;
    }
    
    int main(){
        cin>>n>>q;
        for(int i=1;i<n;i++)
            scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);        
        for(int i=1;i<=q;i++)
            scanf("%d",&qq[i].qq),qq[i].id=i;
        sort(e+1,e+n);
        sort(qq+1,qq+1+q);
        
        for(int i=1;i<=n;i++)F[i]=i,size[i]=1;
        
        int p=1;
        for(int i=1;i<=q;i++){
            while(qq[i].qq>=e[p].w && p<=n-1){
                int u=e[p].u,v=e[p].v;
                bing(u,v);
                p++;
            }
            ans[qq[i].id]=sum;
        }
        for(int i=1;i<=q;i++)
            cout<<ans[i]<<" ";
    }

转载于:https://www.cnblogs.com/zsben991126/p/11507967.html

发表评论取消回复

表情：

评论列表（有 0 条评论，62人围观）

还没有评论，来说两句吧...

相关阅读

相关【离线/并查集】CF1213 G

想起来好久没写题解了，随便写一下把感觉写多了div3后面的题就变得简单了，div3似乎没什么思维含量，甚至有时候能开出div3的2100.... 心血来潮写一下这个\18

待我称王封你为后i/ 2024年03月27日 18:33/ 0 赞/ 94 阅读

相关【MST+离线】CF1851 G

[Problem - G - Codeforces][] 题意： ![721e7beffa0846be9ac132457e59015c.png][] ![92bc92a7

刺骨的言语ヽ痛彻心扉/ 2024年03月22日 21:20/ 0 赞/ 84 阅读

相关离线+生成树+并查集——cf1213G

include<bits/stdc++.h> using namespace std; define N 200005 define ll lo

悠悠/ 2023年10月11日 09:09/ 0 赞/ 63 阅读

相关排序+并查集——cf1213F

/ 有向边(pi,pi+1)，形成链后进行dfs,求出dfs序一个联通块内的元素必须是同一个字符，如果最后的联通块个数<k,说明不行 /

红太狼/ 2023年10月11日 09:04/ 0 赞/ 63 阅读

相关并查集 +最小生成树

并查集：并查集简单来说就是数据分类，怎么分呢，初始把数组 pre\[i\] = i 设定，表示自己归属于自己，如果A是B的老大，那么pre\[A\] = A， pre\

╰半夏微凉°/ 2022年06月10日 00:07/ 0 赞/ 220 阅读

相关 HDU 1213 How Many Tables (并查集)

//题意自己看，不会度娘 include <stdio.h> include <string.h> int a[1050]; int

一时失言乱红尘/ 2022年06月05日 01:55/ 0 赞/ 161 阅读

相关并查集 HDU__1213 How Many Tables

How Many Tables Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

左手的ㄟ右手/ 2022年05月26日 06:54/ 0 赞/ 93 阅读

相关 HDU - 1213 How Many Tables （并查集）

How Many Tables Problem Description Today is

╰+攻爆jí腚メ/ 2022年05月17日 05:46/ 0 赞/ 162 阅读

相关并查集-HDU 1213-How Many Tables

并查集-HDU 1213-How Many Tables -------------------- 题目链接：[How Many Tables][]

深藏阁楼爱情的钟/ 2022年05月15日 01:53/ 0 赞/ 159 阅读

相关 HDU-1213 Ignatius birthday 【并查集】题解

目录 1.题目 2.题意 3.思路 4.代码 1.题目 To

一时失言乱红尘/ 2021年08月29日 16:45/ 0 赞/ 324 阅读