题目重点：按request和child身份聚合，每个子树结果只接纳一次。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 稳定有根树，每节点知道直接children且ID唯一，无环或共享子节点；消息有request_id、sender、kind与payload。节点可信，允许重复、乱序与有限丢失。
- 同一request的parent固定，完成结果可缓存重发。永久节点故障会导致未完成；timeout不是故障证明。示例内存状态，崩溃恢复需持久化且拓扑变动须新epoch。
解题路线
- 收到首次request建立parent/replies/result，向每个child发相同request ID。叶结果为(id,empty children)，向parent回传；root parent=None，不向自己回传。
- reply以child ID为key首次接纳，重复不累计。所有child都有结果时按原children顺序组装完整拓扑，数量可递归统计或直接返回count字段。不能只全局visited node set，多个请求必须隔离，reply发送方也必须确属children。
- 丢request由parent重发未收到结果的child，丢reply由child收到重复request时发缓存result；timer也可重发。进行中重复request推动尚未完成children，不重置已收到replies。
- 迟到reply带旧request/epoch不能混进新任务；同一child重复结果内容改变应视协议错误或拓扑版本失配，本训练可信稳定树只取第一份。有限丢失+最终投递保证终止，永久断网需要返回incomplete及已知未响应节点而非正确总数。
- 输出整个树会让每层重复携带子树内容，若仅要count应只传聚合整数；大树拓扑可由各节点独立写结果到manifest，root返回引用，降低链形树消息字节放大。
手动走一遍
root有a/b，a子树count3，b子树count2，root总6。a reply收到两次仍只计3，不产生9。root已完成但其reply给上级丢失，重复request返回缓存拓扑；再次从头count会重复工作且可能混入变化。随机树两轮独立request在早期丢包/duplicate/reorder后最终可靠投递，与静态邻接遍历核对完整拓扑和节点数。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class Node:
def __init__(self,identity,children):
self.identity=identity;self.children=tuple(children);self.requests={}
if len(set(self.children))!=len(self.children):raise ValueError('duplicate child')
def receive(self,request_id,sender,kind,payload=None):
if kind=='request':
if request_id not in self.requests:
self.requests[request_id]=dict(parent=sender,replies={},result=None)
state=self.requests[request_id]
if sender!=state['parent']:raise ValueError('tree parent changed')
if state['result'] is not None:return self._reply(request_id,state)
if not self.children:
state['result']=(self.identity,());return self._reply(request_id,state)
return self.retry(request_id)
if kind!='reply' or request_id not in self.requests:return []
state=self.requests[request_id]
if sender not in self.children:return []
if sender not in state['replies']:state['replies'][sender]=payload
if state['result'] is None and len(state['replies'])==len(self.children):
state['result']=(self.identity,tuple(state['replies'][c] for c in self.children))
return self._reply(request_id,state)
return []
def _reply(self,request_id,state):
return [] if state['parent'] is None else [(state['parent'],request_id,self.identity,'reply',state['result'])]
def retry(self,request_id):
state=self.requests[request_id]
if state['result'] is not None:return self._reply(request_id,state)
return [(child,request_id,self.identity,'request',None) for child in self.children if child not in state['replies']]
def result(self,request_id):return self.requests[request_id]['result']
def count(tree):return 1+sum(count(child) for child in tree[1])
复杂度
无失败N节点、h高度，request/reply O(N)消息；仅count payload O(N)总字节（固定宽度计数近似），完整嵌套拓扑总传输最坏O(Nh)，链形O(N²)。延迟至少往返高度×链路延迟，重试倍率另计；保留R请求结果需要回收策略。
易错点与追问
容易失分的边界
- 按消息到达次数累加导致重复统计。
- 先把节点标visited再忽略重复request，可能永远不能补回丢失reply。
- 将无环树算法直接用于有环cluster会死锁或重复子树。
继续深挖
- 节点崩溃后如何用持久request state恢复，哪些结果可重新算？
- 拓扑在查询期间变化，怎样用epoch/snapshot定义统计时刻？
