这次的题不知道为啥很多题都是前几天的一场组队赛做过的题（可能教练想检测我们的补题情况），所以重复的题就不写题解了，重复题目题解戳这里，主要写一下其余几题的题解吧。虽然很多题都做过，但是也不是一遍就过，这次主要出现的问题就是数组开小了，比如链式前向星建无向图要开两倍于点数的数组，debug时调小数组，提交时忘记改回来等等，这些错误都是可以避免的。
题目来源是：2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)，题目链接

A – Radio Prize（树形dp+换根dp）

题意

给定一棵无根树，树上每个节点有点权 $t_i$，两点之间有边权 $w_i$。定义从 $u$ 到 $v$ 的距离 $d_{u,v}$d ，为从 $u$ 到 $v$ 路径的边权和，花费为 $P = (t_u + t_v) * d_{u,v}$，对每个点，都要求出到其他点花费的总和。

题目分析

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e6 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;

int h[maxn], to[maxn], w[maxn], ne[maxn], idx, n;
LL sub[maxn], subval[maxn], allval, ans[maxn], ansval[maxn], dotval[maxn];//sub 个数 subval 点权和  ans 所有点到当前距离和  ansval 距离和权值乘积和
void add(int x, int y, int z) {
    to[idx] = y;
    ne[idx] = h[x];
    w[idx] = z;
    h[x] = idx++;
}

void dfs(int x, int fa) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = to[i];
        if (j == fa) continue;
        dfs(j, x);
        sub[x] += sub[j];
        subval[x] += subval[j];
        ans[x] += ans[j] + sub[j] * w[i];
        ansval[x] += ansval[j] + subval[j] * w[i];
    }
    sub[x]++;
    subval[x] += dotval[x];
}

void dfs2(int x, int fa) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = to[i];
        if (j == fa) continue;
        ans[j] = ans[x] - sub[j] * w[i] + (n - sub[j]) * w[i];
        ansval[j] = ansval[x] - subval[j] * w[i] + (allval - subval[j]) * w[i];
        dfs2(j, x);
    }
}

int main(int argc, char const *argv[]) {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) {
        cin >> dotval[i];
        allval += dotval[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    dfs(1, -1);
    dfs2(1, -1);
    for (int i = 1; i <= n; i++) cout << ans[i]*dotval[i] + ansval[i] << endl;
    return 0;
}

C – Coloring Contention（最短路）

题意

Alice和Bob玩游戏，Alice给图的边染色，可以染蓝或者红，Bob任选一条路径从1走到n，走路径上颜色转换次数最少的一条路径（红变蓝算一次，蓝变红算一次），要你帮Alice染色使得Bob所选路径转换次数最大，输出次数。

题目分析

一开始看到求最小值的最大值问题，考虑是否二分答案，发现二分答案很难check，又仔细想了一下，Alice染色只要每条边都红蓝间隔着染，就会让Bob所选路径转换次数最大了，那么Bob会选转换次数最少的，即最短路径，故此题就是求1-n的最短路径，输出最短路径-1，dijkstra模板题。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e6+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int n, m;
int ne[maxn], to[maxn], h[maxn], idx, dis[maxn];
bool vis[maxn];
void add(int a, int b) {
    to[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dijkstra(int st) {
    memset(dis, 0x3f, sizeof dis);
    dis[st] = 0;
    priority_queue<PII> q;
    q.push({0,st});
    while(q.size()){
        auto now = q.top();
        q.pop();
        if(vis[now.second]) continue;
        vis[now.second] = 1;
        for(int i = h[now.second]; i != -1; i = ne[i]) {
            int j = to[i];
            if(dis[j] > dis[now.second] + 1) {
                dis[j] = dis[now.second] + 1;
                q.push({-dis[j],j});
            }
        }
    }
}

int main(int argc, char const *argv[]) {
    memset(h, -1, sizeof(h));
    cin >>n >>m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dijkstra(1);
    cout << dis[n] - 1 << endl;
    return 0;
}

D – Dividing By Two

题意

给你a和b，每次可以对a进行两种操作：+1或者除以2，但是只有a为偶数时才能进行除2操作，要你求最小操作次数让a变成b。

题目分析

由于题目中使a变大只有+1操作，变小只有/2操作，故判断a和b的大小，若a<=b，最小操作数就是b-a。否则，循环一下，不停将a除2直到a小于b（注意a若为奇数要先+1再除2），再将a加到和b一样大，输出操作数。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;

int main(int argc, char const *argv[]) {
    int a, b, ans = 0;
    cin >> a >>b;
    if(a <= b) cout << b - a <<endl;
    else {
        while(a > b) {
            if(a % 2 == 0) a/=2;
            else a++;
            ans++;
        }
        cout << ans + b - a <<endl;
    }
    return 0;
}

E – Rainbow Strings

题意

给你一个字符串，找出其所有子串满足子串中任意两个字符都不相同，注意这里子串的不同定义为：只要在原串中下标不同即可，即就算两个子串长得一样，但是在原串中下标有一个不一样就视为不同，空串也作为一个子串。答案可能很大，模11092019。

题目分析

统计每个字符出现的次数，子串要求没有一个字符相同，那么就相当于每个字符取0个或者取1个，由于下标不同就视为不同的串，故满足的子串数量就是每个（字符数量+1)再相乘。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const int mod = 11092019;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
LL tong[50];
char s[maxn];
int main(int argc, char const *argv[]) {
    cin >> s;
    int n;
    n = strlen(s);
    for(int i = 0; i < n; i++) {
        tong[s[i] - 'a'] ++;
    }
    LL ans = 1;
    for(int i = 0; i <= 25; i++)
        if(tong[i] != 0)
        ans = (ans*(tong[i]+1)) % mod;
    cout << ans%mod << endl;
    return 0;
}