题目理解

我们有一棵树（N 个点，N-1 条边），每个点是一个房间，每个房间有若干条边（过道）按顺时针排列。

每个房间有一个激光笔，初始指向第一条边。

移动规则：

1. 顺时针旋转激光笔到指向下一条边
2. 沿着激光笔指的方向走过道
3. 重复

有 Q 个询问，每个给 K，从房间 1 出发，走 K 步后到哪个房间。

---

关键点

• 这是一个树结构
• 每个点的出边是循环的
• 移动规则是确定性的：每次走到下一个邻居，然后旋转激光笔
• K 很大（最大 10¹⁵），不能模拟

---

观察

从房间 u 到邻居 v 后：

• 在 v 的房间中，激光笔会指向哪条边？
• 由于 v 的边是按顺时针排列的，当我们从 u 走到 v 时，在 v 的边列表中，u 是某个位置
• 然后激光笔会指向 u 的下一条边（循环）

所以整个移动过程形成一个确定性的有限状态自动机，状态是 (当前房间, 当前激光笔位置)。

---

状态表示

设每个点 u 的邻居列表是 adj[u]（按顺时针顺序）。

定义状态为 (u, i)，表示：

• 当前在房间 u
• 激光笔指向 adj[u] 的第 i 条边（从 0 开始编号）

那么状态转移：

• 从 (u, i) 出发，会走到 v = adj[u][i]
• 在 v 中，找到 u 在 adj[v] 中的位置 j
• 然后激光笔会指向 adj[v] 中 j 的下一个位置 (j+1) mod deg(v)
• 所以下一个状态是 (v, (j+1) mod deg(v))

---

问题转化

我们有一个状态图，节点数是 O(N × 平均度数)，但 N 最大 8×10⁵，总状态数可能很大。

但是，由于每个点 u 的每个出边 i 对应唯一状态，总状态数 = 所有点的度数之和 = 2×(N-1) = O(N)。

所以状态数是 2N 级别。

---

算法思路

1. 预处理每个点的邻居列表和每个邻居在列表中的位置
2. 建立状态转移图：state = (当前节点, 出边索引) → 下一个状态
3. 由于 K 很大，需要用倍增法（二进制提升）
   • 令 next[state] = 走 1 步到达的状态
   • 令 jump[state][k] = 走 2^k 步到达的状态
4. 对每个查询 K，用二进制分解快速求出走 K 步后的状态

---

状态编码

为了节省空间，我们可以将状态编码为整数： state_id = (u 的全局编号) × (最大度数) + (出边索引) 但最大度数可能很大，不好。

更好的方法：对每个点 u，状态就是 (u, idx)，我们用一个二维数组或映射来存储转移。

实际上，因为每个点 u 的出边索引范围是 0 到 deg(u)-1，我们可以：

• 对每个点 u 预处理它的所有状态的转移
• 总状态数 ≤ 2N，可以用一维数组存储，编号从 0 到 total_states-1

---

代码框架

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;

int main() {
    int N, Q;
    cin >> N >> Q;
    
    vector<vector<int>> adj(N);
    // pos_in_neighbor[u][v] 表示 u 在 v 的邻居列表中的位置
    vector<vector<int>> pos_in_neighbor(N);
    
    for (int u = 0; u < N; u++) {
        int k;
        cin >> k;
        adj[u].resize(k);
        for (int j = 0; j < k; j++) {
            cin >> adj[u][j];
            adj[u][j]--; // 转为0-based
        }
    }
    
    // 预处理每个邻居在对方列表中的位置
    for (int u = 0; u < N; u++) {
        pos_in_neighbor[u].resize(adj[u].size());
        for (int idx = 0; idx < adj[u].size(); idx++) {
            int v = adj[u][idx];
            // 在 v 的邻居列表中找 u
            for (int j = 0; j < adj[v].size(); j++) {
                if (adj[v][j] == u) {
                    pos_in_neighbor[u][idx] = j;
                    break;
                }
            }
        }
    }
    
    // 分配状态编号
    vector<int> state_start(N+1, 0);
    int total_states = 0;
    for (int u = 0; u < N; u++) {
        state_start[u] = total_states;
        total_states += adj[u].size();
    }
    state_start[N] = total_states;
    
    // next_state[state] = 走1步到达的状态编号
    vector<int> next_state(total_states);
    for (int u = 0; u < N; u++) {
        for (int idx = 0; idx < adj[u].size(); idx++) {
            int v = adj[u][idx];
            int j = pos_in_neighbor[u][idx];
            int next_idx = (j + 1) % adj[v].size();
            int current_state = state_start[u] + idx;
            int next_state_id = state_start[v] + next_idx;
            next_state[current_state] = next_state_id;
        }
    }
    
    // 二进制提升预处理
    int LOG = 60; // 因为 K <= 1e15 < 2^60
    vector<vector<int>> jump(LOG, vector<int>(total_states));
    // jump[0] 就是 next_state
    for (int s = 0; s < total_states; s++) {
        jump[0][s] = next_state[s];
    }
    for (int i = 1; i < LOG; i++) {
        for (int s = 0; s < total_states; s++) {
            jump[i][s] = jump[i-1][jump[i-1][s]];
        }
    }
    
    // 初始状态：在房间0（原房间1），激光笔指向第一条边（索引0）
    int start_state = state_start[0] + 0;
    
    // 处理查询
    while (Q--) {
        ll K;
        cin >> K;
        
        int state = start_state;
        for (int b = 0; b < LOG; b++) {
            if (K >> b & 1) {
                state = jump[b][state];
            }
        }
        
        // 从状态编号还原房间号
        // 找 state 属于哪个点 u
        int u = 0;
        while (state_start[u+1] <= state) u++;
        cout << u + 1 << "\n"; // 转回1-based
    }
    
    return 0;
}

---

复杂度分析

• 预处理：O(N × 平均度数) = O(N)
• 二进制提升：O(N log K)
• 每个查询：O(log K)
• 总复杂度：O(N log K + Q log K)，可以接受

---

样例验证

样例输出与题目一致。

这个解法利用状态机和二进制提升，能够高效处理大规模数据和查询。