Codeforces Round 756 (Div. 3)(E2,F)

题意
给定一个n点n-1条边的树，一个人在1号点，他的朋友们在其他点，每过一秒，每个人都可以移动一步，问这个人在走到任意叶子节点的过程中是否能不被抓住，如果不能，那么找到至少需要几个朋友在树上。

思路
用*depth[i]表示点 i 的节点深度，用d[i]*表示点 i 该点距离最近的朋友的距离，因为是一棵树，因此从1号点到任意的叶子节点都只会有一条路，所以对于从1号点到任意叶子节点的路径中，如果存在$d[i]\le depth[i]$,即这个人的朋友会比这个人先到达这个点，他的朋友可以在这个点拦住他，那么就说明这条路径不能走到1号点，然后我们统计一下有几条路被挡住了就行了

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10,INF=1e9;

int x[N],d[N],depth[N];
vector<vector<int>>g(N);
int ans;

void dfs(int u,int fa)
{
    if(u!=1)depth[u]=depth[fa]+1;
    for(auto j:g[u])
    {
        if(j==fa)continue;
        dfs(j,u);
    }
}
void dfs1(int u,int fa)
{
    if(d[u]==0)return;
    int t=INF;
    for(auto j:g[u])
    {
        if(j==fa)continue;
        dfs1(j,u);
        t=min(t,d[j]);
    }
    d[u]=t+1;
}
bool dfs2(int u,int fa)
{
    if(d[u]<=depth[u]){ans++;return 0;};
    if(g[u].size()==1&&u!=1)return 1;

    bool f=0;
    for(auto j:g[u])
    {
        if(j==fa)continue;
        f|=dfs2(j,u);
    }
    return f;
}
void solve()
{
    ans=0;
    int n,k;cin>>n>>k;
    for(int i=0;i<=n;i++)d[i]=INF,depth[i]=0,g[i].clear();

    for(int i=0;i<k;i++)cin>>x[i],d[x[i]]=0;
    for(int i=0;i<n-1;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1,0);//找到每个点的深度
    dfs1(1,0);//找到每个点距离最近的朋友的距离
    if(dfs2(1,0))cout<<-1<<"\n";//判断是否存在一条从1号点走到任意叶子节点的路径
    else cout<<ans<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int T;cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

题意
给定一个长度为n的序列a和一初始值ss，对于任意a[i]的范围为$(-1e9\le a[i]\le 1e9)$要求找到一个最长的连续子序列，满足这一段连续子序列的任意前缀和的最小值大于等于-ss , 即将ss放到这一段连续子序列的最前面，对于这一段连续子序列的任意前缀和要大于等于0。问最长的子序列的长度，输出该长度的头和尾的下标

思路
首先，我们对于原序列a求一遍前缀和，前缀和中是可能出现负数的，此时枚举左边界，右边界不存在单调性，因此我们不能二分来查找右边界，这个时候我们可以用st表预处理出来任意一段前缀和中的最小值，然后我们二分的check就是固定了左边界后，此时的mid，即对于$i\sim mid$这一段的前缀和中的最小值加上ss后是否大于等于0，此时二分的右边界就具有单调性了，这个时候就可以二分查找对于每个i的最大的右边界了，有一些细节看代码吧

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;

ll st[N][20];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        ll n, ss;
        cin >> n >> ss;
        vector<ll> a(n + 1, 0), s(n + 1, 0);
        for (int i = 1; i <= n; i++)
            cin >> a[i], s[i] = s[i - 1] + a[i];

        for (int j = 0; j < 20; j++) // st表初始化
            for (int i = 1; i <= n; i++)
                st[i][j] = 0;

        for (int j = 0; j < 20; j++) // st表预处理出来任意一段前缀和的最小值
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
            {
                if (!j)st[i][j] = s[i];
                else st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }

        int ans_len = 0, ansl = -1, ansr = -1;
        auto check = [&](int l, int r)
        {
            int len = 0;
            while ((1 << len + 1) <= r - l + 1)len++;
            return min(st[l][len], st[r - (1 << len) + 1][len]) - s[l - 1] + ss >= 0;
            //注意这里任意一段的前缀和要减去1~l-1这一段然后再加上ss
        };
        for (int i = 1; i <= n; i++)
        {
            int l = i, r = n;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (check(i, mid))l = mid;
                else r = mid - 1;
            }
            if (check(i, r) && r - i + 1 > ans_len)
            {
                ansl = i;
                ansr = r;
                ans_len = r - i + 1;
            }
        }
        if (ans_len)
            cout << ansl << " " << ansr << "\n";
        else
            cout << -1 << "\n";
    }
    return 0;
}