Codeforces Round 926 (Div. 2)

A.

升序排列再求和

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;
#define inf 0x3f3f3f3f

void solve() {
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    int sum=0;
    for(int i=2;i<=n;i++){
        sum+=a[i]-a[i-1];
    }
    cout<<sum<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

B.

样例已经给出了做法
2*n-2个方格是2的贡献，2个方格是1的贡献

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;
#define inf 0x3f3f3f3f

void solve() {
    int n,k;cin>>n>>k;
    if((2*n-2)*2>=k)cout<<(k+1)/2<<'\n';
    else cout<<(2*n-2+(k-(2*n-2)*2))<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

D.

任意两点的简单路径，要找两点的公共祖先
设两点a，b，若a、b各自到公共祖先的路径上的危险节点小等于1，那么这条简单路径一定合法
处理出所有节点作为公共祖先节点所能作出的贡献
dp[i][j],表示以i为公共祖先节点，在以i为根的子树中危险节点为j的方案数

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=3e5+10;
#define inf 0x3f3f3f3f

const int mod=998244353;
vector<int>e[N];
int n,dp[N][3];
void dfs(int now,int fa){
    for(auto it:e[now]){
        if(it==fa)continue;
        dfs(it,now);
        dp[now][0]=1;
        dp[now][1]=(dp[now][1]*(dp[it][0]+dp[it][1]))%mod;
        dp[now][2]=(dp[now][2]+dp[it][1]+dp[it][2])%mod;
    }
}
void solve() {
    cin>>n;
    for(int i=1;i<=n;i++){
        e[i].clear();dp[i][0]=dp[i][1]=1;dp[i][2]=0;
    }
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,-1);
    cout<<(dp[1][0]+dp[1][1]+dp[1][2])%mod<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}