目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

有 \(n\) 个城市，\(m\) 条无向边，每条边都有一个权值 \(k\)；

之后 \(Q\) 次强盗来袭，只有边权大于等于 \(x\) ，这条边才可以不受伤害，求每次强盗来袭可以抵挡住攻击的边的条数

State

\(1<=T<=10\)

\(1<=n<=10^{5}\)

\(1<=m<=2*10^5\)

\(1<=Q<=2*10^5\)

\(1<=k<=10^9\)

\(1<=p<=10^9\)

Input

1
5 5 3
1 2 2
2 3 3
3 4 1
4 5 1
5 1 3
3
2
1

Output

2
6
10

Solution

题目考察连通块，初始状态时每一个城市都是一个连通块，当有破坏 \(x\)，到达时，将边权大于等于 \(x\) 的城市相连接，这样连通块内的城市个数记为 \(N\)，此连通块对答案的贡献就是 \(C_N^2\) ；

剩下的就是对于每一个 \(x\)，找到所有的连通块，连通块可以用并查集解决，而样例十分友好，提醒我们将 \(x\) 降序排列，可以利用离线做法，这样就不需要使用 \(Q\) 遍并查集了

Code

const int N = 2e5 + 5;

    ll n, m, _;
    int i, j, k;
    struct Node
    {
        int u, v, w;
        void read(){ sddd(u, v, w); }
        bool operator<(Node o){
            return w > o.w;
        }
    }a[N];
    pii c[N];
    int fa[N], sz[N];
    ll ans[N];
    ll now = 0;

void calc(ll x, ll y)
{
    if(y != 1){
        now -= y * (y - 1) / 2;
    }
    if(x != 1){
        now -= x * (x - 1) / 2;
    }
    x += y;
    now += x * (x - 1) / 2;
}

int Find(int x)
{
    if(x == fa[x]) return x;
    else return fa[x] = Find(fa[x]);
}

void Union(int x, int y)
{
    int nx = Find(x), ny = Find(y);
    if(nx != ny){
        fa[nx] = ny;
        calc(sz[ny], sz[nx]);
        sz[ny] += sz[nx];
    }
}

signed main()
{
    //IOS;
    rush(){
        sddd(n, m, k);
        rep(i, 1, n){
            fa[i] = i;
            sz[i] = 1;
        }
        now = 0;
        rep(i, 1, m){
            a[i].read();
        }
        rep(i, 1, k){
            sd(c[i].fi);
            c[i].se = i;
        }
        sort(a + 1, a + 1 + m);
        sort(c + 1, c + 1 + k, greater<pii>());
        int p = 1;
        for(int i = 1; i <= k; i ++){
            int u, v, w;
            u = a[p].u, v = a[p].v, w = a[p].w;
            while(p <= m && w >= c[i].fi){
                Union(u, v);
                p ++;
                u = a[p].u, v = a[p].v, w = a[p].w;
            }
            ans[c[i].se] = now;
        }
        rep(i, 1, k) pll(ans[i]);
    }
    //PAUSE;
    return 0;
}