从期末中活着出来了qwq

1.Apple Tree

链接
一道搜索与树的题（当然也可以用树型dp）

思路：其实就是每个苹果可以到达那几个节点，然后一组询问有两个苹果，把这两个苹果可以到达的节点相乘就行了

主要代码不会写，考完期末回来建树都快不会了qwq

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define rep(i,a,n) for (int i = a;i < n;i ++ )
#define per(i,a,n) for (int i = n - 1;i >= a;i --)
#define endl(x) for (int i = 0; i < x; i ++ ) cout << endl
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef double db;
typedef long long LL;
typedef unsigned long long ULL;
LL gcd(LL a,LL b) {return b ? gcd(b, a % b) : a;}
//head

//debug...
//cout << "debug......" << endl;
//cout << "test......" << endl;
int n, q;
vector<int> g[2 << 17];
int ch[2 << 17];

int dfs(int u,int p)
{
    bool fn = false;
    ch[u] = 0;
    for(int v : g[u])//遍历节点u链接的所有节点 
        if(v != p)//不往回走
        {
            fn = true;//如果存在其他节点，代表这u节点不是叶子节点
            ch[u] += dfs(v,u);
        }
    if(!fn) ch[u] = 1;//如果是叶子节点返回1
    return ch[u];//这个其实也可以去掉改成void
}

void solve(){
    cin >> n;
    rep(i, 0, n) g[i].clear();
    rep(i, 1, n){
        //储存树的信息
        int u, v; cin >> u >> v;
        u --, v --;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(0, -1);//设0有一个为-1的邻居

    cin >> q;
    rep(i, 0, q){
        int x, y; cin >> x >> y;
        //查找然后算
        cout << 1LL * ch[--x] * ch[--y] << endl;
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T; cin >> T;//注意题给条件，这个T可能要初始化为1
    while (T -- ) solve();

    return 0;
}

2.Wooden Toy Festival

链接
cf里面少见的二分doge

思路：很多最大最小值问题和最小最大值问题都可以用二分，这道题也不例外，主要是通过二分确定最长间隔是多少。
分配摸具的策略是这样，假定最长间隔是mid，第一个摸具分配在最小图案+mid处，第二个模具分配在最大图案-mid处，
看剩下一个模具能不能照顾剩下区间的图案，如果满足这个条件的话大于等于mid的最大间隔均满足（二分）。

详细可以看代码qwq

 #include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define rep(i,a,n) for (int i = a;i < n;i ++ )
#define per(i,a,n) for (int i = n - 1;i >= a;i --)
#define endl(x) for (int i = 0; i < x; i ++ ) cout << endl
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef double db;
typedef long long LL;
typedef unsigned long long ULL;
LL gcd(LL a,LL b) {return b ? gcd(b, a % b) : a;}
//head

//debug...
//cout << "debug......" << endl;
//cout << "test......" << endl;

void solve(){
    int n; cin >> n;
    VI a(n);

    rep(i, 0, n) cin >> a[i];
    sort(all(a));

    auto check = [&](int mid){
        int t1 = a[0] + mid;
        int t2 = a[n - 1] - mid;

        int mn = 0x3f3f3f3f, mx = 0;
        for (auto x : a){
            if (abs(t1 - x) <= mid || abs(t2 - x) <= mid) continue;
            mn = min(mn, x);
            mx = max(mx, x);
        }

        return mx - mn <= 2 * mid;
    };

    int l = 0, r = 1e9 + 1;

    while(l < r){
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << r << endl;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T; cin >> T;//注意题给条件，这个T可能要初始化为1
    while (T -- ) solve();

    return 0;
}