D - Bonus EXP

简单DP
设置 $dp[i][j]$ 代表考虑选择前 $i$ 个元素击杀，击杀次数的奇偶性是 $j(1 or 0)$的最大值。
考虑转移：
分类讨论 $i$ 元素, 选与不选 以及 奇数次与偶数次 共 $2*2$ 种情况

时间复杂度为 $O(N^2)$
可以设置 $g[1or0]$ 表示 max { $f[j][1or0]$ }, 将时间优化到 $O(N)$

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        ll x;
        cin >> x;
        if (i == 1){
            f[i][1] = x;
            f[i][0] = 0; //只能不选
            g[1] = max(g[1], f[i][1]);
            g[0] = max(g[0], f[i][0]);
        }else{
            f[i][1] = man(x + g[0], g[1]);
            f[i][0] = man(x * 2 + g[1], g[0]);
            g[1] = max(g[1], f[i][1]);
            g[0] = max(g[0], f[i][0]);
        }
    }
    cout << max(g[0], g[1]) ;
}

E - Sightseeing Tour

对于每次询问考虑暴力做法。
枚举每条边的经过顺序的双向边的方向，然后使用一些边连接所有的边，从而构成从1出发到n结束的最优值。
固定边的大小一定不变，因此最优化中间的桥梁路径的大小，也就是两两边端点 $i_u - j_v$ 的最短路，答案就是最优加和。
任意两点间的最短路可以用 Floyd $O(N^3) = 400^3$ 预处理，然后 $O(1)$ 查询。
那么询问一次的时间就是 $O(k! * 2^k)$，总查询时间就是 $O(Q*k!*2^k) = 1.1e8$
总结：Floyd + 全排列
代码如下

ll E[M][2], w[M];
ll f[N][N];

void solve() {
    int n, m;
    cin >> n >> m;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i ++ ) f[i][i] = 0;
    for (int i = 1; i <= m; i ++ ){
        ll a, b, c;
        cin >> a >> b >> c; 
        E[i][0] = a, E[i][1] = b, w[i] = c;
        f[a][b] = f[b][a] = min(f[a][b], c);
    }
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    int q; cin >> q;
    while (q -- ){
        int len;
        cin >> len;
        vector<int> b(len + 1);
        ll more = 0;
        for (int i = 1; i <= len; i ++ ) cin >> b[i], more += w[b[i]];
        sort(b.begin() + 1, b.end()); //先排序再全排列
        ll res = 1e18;
        do{
            for (int i = 0; i < 1 << len; i ++ ){ //状态压缩
                ll cost = 0;
                cost += f[1][E[b[1]][i & 1]] + f[E[b[len]][((i >> (len - 1)) & 1) ^ 1]][n];
                for (int j = 1; j < len; j ++ )
                    cost += f[E[b[j]][((i >> j - 1) & 1) ^ 1]][E[b[j+1]][(i >> j) & 1]];
                res = min(res, cost);
            }
        }while (next_permutation(b.begin() + 1, b.end()));
        cout << res + more << '\n';
    }
}

F - Gather Coins

最长上升子序列 $(LIS)$模板题
难点在于记录路径

int h, w, n;
pair<int, int> coins[N];
int f[N];

void solve()
{
    cin >> h >> w >> n;
    for (int i = 0; i < n; i ++ ) cin >> coins[i].first >> coins[i].second;

    sort(coins, coins + n);
    vector<int> f(n, 1e9), id(n, -1), pre(n, -1);
    for (int i = 0; i < n; i ++ ){
        int x = coins[i].second;
        int it = upper_bound(f.begin(), f.end(), x) - f.begin();
        f[it] = x;
        id[it] = i; 
        pre[i] = it ? id[it - 1] : -1;
    }

    int m = n - 1;
    while (id[m] == -1) -- m;
    int now = id[m];
    vector<pair<int, int>> path(1, {h, w});
    while (now != -1){
        path.push_back(coins[now]);
        now = pre[now];
    }
    path.push_back(make_pair(1, 1));
    reverse(path.begin(), path.end());
    string s;
    for (int i = 1; i < path.size(); i ++ ){
        int d = path[i].first - path[i - 1].first;
        int r = path[i].second - path[i - 1].second;
        while (d -- ) s.push_back('D');
        while (r -- ) s.push_back('R');
    }
    cout << m + 1 << '\n';
    cout << s << '\n';
}

G - As far as possible

要求从 $1$ 出发经过必经点再到 $1$结束，不妨设置成 $1$ 为根的树。
A被动，B主动，所以从B出发思考。
对于 $k:1-n$
$k = 1$ 时，B一定选择深度最深的点使得最小值最大化
但是当 $k = 2$ 时，就不一定选择次深点，因为前面最深和现在次深的路径可能会重复，使得次深带来的贡献降低。
假设次深与最深重复，那么次深的实际贡献就是去掉重复之后剩余的部分。
然后，你就会惊奇的发现——这不就是树链剖分吗
先找到所有中链，然后排序取最大

ll n, d[N], fa[N], son[N]; // son记录重节点
vector<pair<int, int>> edge[N];

void dfs_1(int x) // 求重节点son
{
    for (auto [y, v] : edge[x])
        if (y != fa[x])
        {
            fa[y] = x;
            dfs_1(y);
            if (d[x] < d[y] + v){  
                d[x] = d[y] + v;
                son[x] = y;
            }
        }
}

int top[N];

vector<ll> ans;

void dfs_2(int x, int t) // 求top 以及 中链
{
    top[x] = t;
    for (auto [y, v] : edge[x])
        if (y != fa[x])
        {
            dfs_2(y, y == son[x] ? t : y); 
            if (y == top[y])
                ans.push_back(d[y] + v); 
        }
}

void solve()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }
    // 以1为根
    dfs_1(1); 
    dfs_2(1, 1);
    ans.push_back(d[1]);
    while (ans.size() < n - 1)
        ans.push_back(0);
    sort(ans.begin(), ans.end(), greater<ll>());
    ll res = 0;
    for (int i = 0; i < n; i++)
    {
        res += ans[i] * 2;
        cout << res << '\n';
    }
}