B

逆序对 循环移位

给一个排列，问每次循环移位一个区间后，序列逆序对奇偶性

交经典结论，换两个相邻元素，保证元素不同，逆序对奇偶反转。循环移位这个区间，相当于把移动到左边，其他不变，也就是交换次。根据的奇偶，即可知道操作完，整个序列逆序对的奇偶。

F

状压 枚举 二分

不大，保留灯管的所有情况最多也不多。考虑枚举所有保留的灯管集合，对每个集合去检查能否区分种数字。检查时直接保存mask&a_i，看结果是否有种，这可以unordered_map实现。但常数有点大，也可以记录每种结果的出现次数，手动维护结果种类数。每次枚举都要清空，值域显然不能暴力清空，考虑用时间戳思想。

这样复杂度还是有点极限，因为多测。

注意到集合大小具有单调性，集合越大，保留灯管越多，越可能区分种数字。考虑二分集合大小。每次只检查大小为的所有集合。这样不会检查所有个集合。只会检查最多个集合，这还是最坏，如果二分的都不接近的话，会更少。

这样跑得飞快，完全不会被卡。

当然还有别的优化，注意到样例其实提示我们，只要用5根灯管就能区分，所以找到只用5根就能区分的方案。把全集设为这个方案，总方案数只有种，枚举所有方案也能过。

#include <bits/stdc++.h>
// #define int long long


using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;

vector<vector<int>>msk(22);
vector<int>num_mask(10);
vector<int>cnt((1<<21)+10),timestamp((1<<21)+10);
int cur=0;
void solve() {
    int n,m;
    cin>>n>>m;
    vector<int>a;
    
    int tot=0;
    for(int i=0;i<n;i++){
        string x;
        cin>>x;
        int all=0;
        for(char c:x){
            int t=c-'0';
            t=num_mask[t];
            all=(all<<7)+t;
        }
        a.push_back(all);
        tot|=all;
    }

    int l=0,r=__builtin_popcount(tot);

    auto check=[&](int x)->bool{
        for(int mask:msk[x]){
            cur++;
            bool ok=1;
            for(int t:a){
                if(timestamp[t&mask]!=cur){
                    timestamp[t&mask]=cur;
                    cnt[t&mask]=0;
                }
                cnt[t&mask]++;
                if(cnt[t&mask]==2){
                    ok=0;
                    break;
                }
            }
            if(ok){
                return 1;
            }
        }
        return 0;
    };
    while(l<=r){
        int m=(l+r)/2;
        if(check(m))r=m-1;
        else l=m+1;
    }
    cout<<l<<'\n';
}


signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1; cin >> T;
    for(int i=0;i<(1<<21);i++){
        int cnt=__builtin_popcount(i);
        msk[cnt].push_back(i);
    }
    num_mask[0]=(1<<6)-1;
    num_mask[1]=(1<<4)+(1<<5);
    num_mask[2]=1+(1<<2)+(1<<3)+(1<<5)+(1<<6);
    num_mask[3]=1+(1<<3)+(1<<4)+(1<<5)+(1<<6);
    num_mask[4]=(1<<1)+(1<<4)+(1<<5)+(1<<6);
    num_mask[5]=1+(1<<1)+(1<<3)+(1<<4)+(1<<6);
    num_mask[6]=1+(1<<1)+(1<<2)+(1<<3)+(1<<4)+(1<<6);
    num_mask[7]=1+(1<<4)+(1<<5);
    num_mask[8]=(1<<7)-1;
    num_mask[9]=1+(1<<1)+(1<<3)+(1<<4)+(1<<5)+(1<<6);

    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}

G

最小生成树 树剖/倍增

图上增加一条边，使得它会出现在所有最小生成树里。问有多少种方案？

树上任意两点之间都可能加边，如果加一条边，能出现在任何一个最小生成树里，那么假设在原图上，跑最小生成树，在树上的路径上的最大边权为，增加的这条边必须边权在[1,w-1]w-1$种选择。

这样就相当于要求，在最小生成树上，求树上所有点对的路径最大边权和。这可以在求最小生成树的同时，并查集维护集合大小，每次一条边如果合并了两个集合，这条边一定是里所有点和里所有点形成的全部点对，路径上边权最大的边。也就是这些点对的答案都是。

但这样的问题是，要求加了一条边后仍是简单图，所以不能重边，也就是原图上存在边的点对，就不能加了。

所以要从把原图上存在边的点对的答案减掉。每条边的答案仍是我们上面的结论，需要是最小生成树上，两个端点的路径上的最大边权。我们需要对原图上所有点，查询生成树上，两点间路径的最大边权。这可以树剖或者倍增。

树剖的话，注意这里是边权，但树剖板子是点权，需要把边权放到一个端点上，如果放到深度较大的点上，查询路径上所有边的最大权值时，会查到上方的那条边，这条边不在路径上，不应该被包含进来。所以查询前需要先取消的权值，查后恢复。

#include <bits/stdc++.h>
#define int long long


using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;
const int mod=1e9+7;

struct tree{
    #define ls u<<1
    #define rs u<<1|1
    struct node{
        int l,r;
        int mx;
    }tr[N<<2];

    void pushup(int u){
        tr[u].mx=max(tr[ls].mx,tr[rs].mx);
    }

    void build(int u,int l,int r){
        tr[u]={l,r,0};
        if(l==r){
            return;
        }
        int mid=(l+r)/2;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(u);
    }

    void modify(int u,int l,int r,int val){
        if(tr[u].l>=l&&tr[u].r<=r){
            tr[u].mx=val;
            return;
        }
        int mid=(tr[u].l+tr[u].r)/2;
        if(mid>=l){
            modify(ls,l,r,val);
        }
        if(r>mid){
            modify(rs,l,r,val);
        }
        pushup(u);
    }

    int query(int u,int l,int r){
        if(l<=tr[u].l&&tr[u].r<=r){
            return tr[u].mx;
        }
        int mid=(tr[u].l+tr[u].r)/2;
        if(r<=mid){
            return query(ls,l,r);
        }
        if(l>mid){
            return query(rs,l,r);
        }
        return max(query(ls,l,r),query(rs,l,r));
    }
}tr;
void solve() {
    int n,m,k;
    cin>>n>>m>>k;

    vector<array<int,3>>e;

    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e.push_back({u,v,w});
    }
    sort(e.begin(),e.end(),[](auto &x,auto &y){
        return x[2]<y[2];
    });

    vector<int>f(n+1),sz(n+1,1);
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    auto &&find=[&](auto &&find,int x)->int{
        if(f[x]==x)return x;
        return f[x]=find(find,f[x]);
    };

    int ans=0;
    vector<vector<pair<int,int>>>g(n+1);
    for(auto &t:e){
        int u=t[0],v=t[1],w=t[2];
        int fx=find(find,u),fy=find(find,v);
        if(fx!=fy){
            f[fx]=fy;
            ans=(ans+(w-1)*sz[fx]%mod*sz[fy]%mod)%mod;
            sz[fy]+=sz[fx];

            g[u].push_back({v,w});
            g[v].push_back({u,w});
        }
    }
//     cout<<ans<<'\n';
    int cnt=0;
    vector<int>sz1;
    for(int i=1;i<=n;i++){
        int fa=find(find,i);
        if(fa==i){
            cnt++;
            sz1.push_back(sz[i]);
        }
    }
    if(cnt==1){
        vector<int>dep(n+1),fa(n+1),sz(n+1,1),son(n+1),ww(n+1);
        auto &&dfs1=[&](auto &&dfs1,int u,int f)->void{
            int mx=0,mxson=0;
            for(auto &[v,w]:g[u]){
                if(v==f)continue;
                dep[v]=dep[u]+1;
                fa[v]=u;
                ww[v]=w;
                dfs1(dfs1,v,u);
                sz[u]+=sz[v];
                if(sz[v]>mx){
                    mx=sz[v];
                    mxson=v;
                }
            }
            son[u]=mxson;
        };
        dfs1(dfs1,1,-1);
        int cnt=0;
        vector<int>top(n+1),dfn(n+1);
        auto &&dfs2=[&](auto &&dfs2,int u,int topf)->void{
//             cout<<u<<' ';
            dfn[u]=++cnt;
            top[u]=topf;
            if(!son[u]){
                return;
            }
            dfs2(dfs2,son[u],topf);
            for(auto &[v,w]:g[u]){
                if(v==fa[u]||v==son[u])continue;
                dfs2(dfs2,v,v);
            }
        };
        dfs2(dfs2,1,1);
//         cout<<'\n';
        tr.build(1,1,n);
        for(int i=1;i<=n;i++){
            tr.modify(1,dfn[i],dfn[i],ww[i]);
//             cout<<ww[i]<<' ';
//             cout<<dfn[i]<<' ';
        }
//         cout<<'\n';

        auto ask=[&](int x,int y)->int{
            int res=0;
            while(top[x]!=top[y]){
                if(dep[top[x]]<dep[top[y]]){
                    swap(x,y);
                }
                res=max(res,tr.query(1,dfn[top[x]],dfn[x]));
                x=fa[top[x]];
            }
            if(dep[x]>dep[y]){
                swap(x,y);
            }
            res=max(res,tr.query(1,dfn[x],dfn[y]));
//             cout<<tr.query(1,dfn[x],dfn[y])<<'\n';
            return res;
        };

        auto lca=[&](int x,int y)->int{
            while(top[x]!=top[y]){
                if(dep[top[x]]<dep[top[y]]){
                    swap(x,y);
                }
                x=fa[top[x]];
            }
            if(dep[x]<dep[y]){
                return x;
            }
            else{
                return y;
            }
        };

        for(auto &t:e){
            int u=t[0],v=t[1];

            int LCA=lca(u,v);
            int tmp=tr.query(1,dfn[LCA],dfn[LCA]);
            tr.modify(1,dfn[LCA],dfn[LCA],0);
            int mx=ask(u,v);
            tr.modify(1,dfn[LCA],dfn[LCA],tmp);
//             cout<<u<<' '<<v<<' '<<mx<<'\n';
            ans=(ans-(mx-1)+mod)%mod;
        }

        cout<<ans<<'\n';
        
    }
    else if(cnt==2){
        int ans=k*sz1[0]%mod*sz1[1]%mod;
        cout<<ans<<'\n';
    }
    else{
        cout<<0<<'\n';
    }
}


signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1; cin >> T;
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}