AtCoder Beginner Contest 218

https://atcoder.jp/contests/abc218

F - Blocked Roads

题意

给定一张 $n$ 个点 $m$ 条边的有向图。对于 $i=1,2,\cdots,m$，求删除第 $i$ 条边后 $1$ 到 $n$ 的最短路。

数据范围：$2\leq n\leq400,1\leq m\leq n\times(n-1)$。

题解

直接做bfs求最短路是 $O(n+m)$ 的，对于 $m$ 条边每条都做显然不行。而 $1$ 到 $n$ 的最短路上至多有 $n-1$ 条边。只需要对这些边重新跑bfs，其它边一定不会影响最短路的长度。

G - Game on Tree 2

题意

给定一棵 $n$ 个点的树。两个人从根节点出发轮流移动，每次走向一个未访问过的相邻的点。最终求出所有访问过的点的点权的中位数，先手希望最大化，后手希望最小化。求双方最优策略下的结果。

数据范围：$1\leq n\leq 10^5$。

题解

容易发现最终一定走向一个叶子结点。那么我们可以处理出每个叶子结点到根的路径上所有点的中位数，然后直接dp。记 $f_i$ 为走到 $i$ 的答案，走向子结点中最大或最小的那个就可以了。中位数可以使用对顶堆维护。

代码

#include <bits/stdc++.h>
using namespace std;
multiset<int> S,T;
void eval()
{
    if(S.size())
    {
        auto it=S.end();it--;
        T.insert(*it);S.erase(it);
    }
    while(S.size()<T.size())
    {
        S.insert(*T.begin());T.erase(T.begin());
    }
}
int val()
{
    auto it=S.end();it--;
    if(S.size()==T.size()+1) return *it;
    return (*it+*T.begin())/2;
}
void insert(int x)
{
    S.insert(x);
    eval();
}
void erase(int x)
{
    auto it=S.end();it--;
    if(*it<x) T.erase(T.lower_bound(x));
    else S.erase(S.lower_bound(x));
    eval();
}
const int N=1e5+5;
int a[N],f[N];
vector<int> g[N];
void dfs(int u,int fa,int d)
{
    insert(a[u]);
    int mn=0x3f3f3f3f,mx=0;
    for(auto v:g[u])
        if(v!=fa)
        {
            dfs(v,u,d+1);
            mn=min(mn,f[v]),mx=max(mx,f[v]);
        }
    if(mx==0) f[u]=val();
    else if(d&1) f[u]=mn;
    else f[u]=mx;
    erase(a[u]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    dfs(1,0,0);
    cout<<f[1]<<'\n';
    return 0;
}