https://codeforces.com/contest/2133

E

交互題感覺只要看給出的詢問次數就能推測出做法。
顯然至少每個點都要進行一次操作1，最多也就少問一個點可以忽略不計，所以剩下的次數就是用來進行操作2的。也就是說每四個點要進行操作2。手玩小樣例，菊花圖，二叉樹，鏈，可以發(fā)現只要把siz大于4的模塊直接截斷，最后剩下的連通塊大小都不超過3，也就是都是一條鏈，一條鏈的情況是直接詢問得出的。（題解寫法有點類似樹鏈剖分，不過本題思維難度不高，主要在于實現難度，每四個點截斷非常好寫）

采用給樹染色的方法，能很容易分類討論一個連通塊的三種情況（截斷點，鏈端點為lca或者鏈端點不為lca）。又因為一個點有效兒子不超過2個，記錄一下就很好寫了。

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define ls(x) (x << 1)
#define int long long
#define endl '\n'
#define rs(x) (x << 1 | 1)
const int N = 2e5 + 7, MOD = 998244353;
int mul(int x, int y) {return 1ll * x * y % MOD;}
int qpow(int x, int y) {
    int res = 1; while(y) {
        if (y & 1) res = mul(res, x);
        x = mul(x, x); y >>= 1;} return res;
}
vector<int> E[N];
vector<pair<int, int>> ans;
int n, col[N], son1[N], son2[N];
void init() {
    ans.clear();
    for (int i = 1; i <= n; i++) 
        son1[i] = son2[i] = col[i] = 0, E[i].clear();
}
void dfs(int x, int fa) {
    int cnt = 0;
    for (int v : E[x]) {
        if (v == fa) continue;
        dfs(v, x);
        if (col[v] == 1) {
            cnt++;
            if (!son1[x]) son1[x] = v;
            else son2[x] = v;    
        }
        else if (col[v] == 2) cnt += 10;
    }   
    if (cnt > 2) col[x] = 3;
    else if (cnt == 2) col[x] = 2;
    else col[x] = 1;
    // cout << x << ' ' << col[x] << " ???" << endl;
}
void dfs0(int x, int fa) {
    if (son1[x]) dfs0(son1[x], x);
    ans.push_back({1, x});
    col[x] = 3;
}
void dfs3(int x, int fa) {
    int p = 0;
    if (col[x] == 1) {
        ans.push_back({1, x});
        if (son1[x]) dfs3(son1[x], x), p = son1[x];
    }
    for (int i : E[x]) {
        if (i == p || i == fa) continue;
        dfs3(i, x);
    }
}
void solve() {
    cin >> n;
    init();
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        E[u].push_back(v); E[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        if (col[i] == 3) ans.push_back({1, i}), ans.push_back({2, i});
    }
    for (int i = 1; i <= n; i++) {
        if (col[i] == 2) {
            dfs0(son1[i], i);
            ans.push_back({1, i});
            int cur = son2[i];
            while(cur) {
                col[cur] = 3;
                ans.push_back({1, cur});
                cur = son1[cur];
            }
        }
    }
    dfs3(1, 0);
    cout << ans.size() << endl;
    for (auto i : ans) {
        cout << i.first << ' ' << i.second << endl;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int T; 
    cin >> T;
    while(T--) solve();
}

F

線段樹優(yōu)化DP