CSP-S开小灶1

居然敢嫌弃Cat的文化课不让Cat来参加半集训！？哼这是不可能的Cat哭给你看！……

A. ZZH的游戏

WA 15：emmm想到了二分，然后判断的时候我没有想到让它贪心地走到尽量小的节点，而是让它尽量跳father，我怕它尽量往小跳反而偏离了终点结束不了游戏，跳不了了就让另一棵树后退到最小的儿子(这或许是WA的原因，因为最小儿子的最小儿子不一定比次小儿子的最小儿子小，但总之还是骗到了15分)，以1为根建树当然跳到根游戏就结束了。

是的是的是的我又鹤了%%%Chen_jr的题解

一开始看到正解上的从s+t开始不行了+1就好迷迷糊糊，这怎么可能比二分快，鹤完代码才知道这个+1指的是在过程中加，意思就是每组数据大模拟只有一次。

保存每个点能到达的最小位置，用它直接作为另一棵树拓展的条件，可以避免会T的后退操作，所以可以要求每个点最多经过一次。

#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
const int maxn = 1e6 + 2;
const int N = 60;
const ll mod = 1e9 + 7;

int T, s, t, n;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct tree 
{
    struct edge 
    {
        int next, to;
    }a[maxn<<1];
    int head[maxn], len;
    void add(int x, int y)
    {
        a[++len].to = y; a[len].next = head[x]; head[x] = len;
    }
    bool vis[maxn];
    int mi = maxn + maxn + maxn;
    priority_queue<int, vector<int>, greater<int> > q;
    void clear()
    {
        for(int i=1; i<=n; i++) head[i] = 0;
        for(int i=1; i<=n; i++) vis[i] = 0;
        len = 0; mi = maxn + maxn + maxn;
        while(!q.empty()) q.pop();
    }
    void build()
    {
        for(int i=1; i<n; i++)
        {
            int x = read(), y = read();
            add(x, y); add(y, x);
        }
    }
    bool expand(int mx)
    {
        bool flag = 0;
        while(!q.empty())
        {
            int x = q.top(); 
            if(x > mx) break;
            q.pop(); vis[x] = 1; flag = 1; mi = min(mi, x);
            for(int i=head[x]; i; i=a[i].next)
            {
                int v = a[i].to; 
                if(vis[v]) continue;
                q.push(v);
            }
        }
        return flag;
    }
    void set(int x) {mi = x; q.push(x);}
}t1, t2;

int solve()
{
    n = read(); t1.build(); t2.build();
    s = read(); t = read();
    int ans = s + t;
    t1.set(s); t2.set(t);
    t1.expand(s); t2.expand(t);
    while(1)
    {
        bool f1 = 1, f2 = 1;
        while(f1 || f2)
        {
            if(t1.mi == 1 && t2.mi == 1) return ans;
            f1 = t1.expand(ans-t2.mi);
            f2 = t2.expand(ans-t1.mi);
        }
        ans++;
    }
}

int main()
{
    T = read();
    while(T--)
    {
        printf("%d\n", solve());
        t1.clear(); t2.clear();
    }
  
    return 0;
}

B. ZZH与背包

枚举一下每个物品选或不选TLE11***鹤个题解去……