树转区间：DFS 欧拉序（in /out 时间戳）

树的子树对应一段连续区间，是线段树能处理的核心前提：

1. 定义 in[u]：第一次访问节点 u 的时间戳；
2. 定义 out[u]：遍历完 u 整棵子树离开时的时间戳；
3. 所有属于 u 子树的节点，它们的 in 编号一定落在区间 \([in[u], out[u]]\)。

举个例子：

1
├─2
└─3

dfs 序：1 → 2 → 回溯 → 3 → 回溯 \(in[1]=1,\ out[1]=3\) \(in[2]=2,\ out[2]=2\) \(in[3]=3,\ out[3]=3\) 子树 1 对应区间 \([1,3]\)，子树 2 对应 \([2,2]\)。

DFS 预处理代码片段

int tim=0;
double w[300005]; // w[u] = ln(节点u当前权值)
int in[300005],out[300005];
vector<int>g[300005];

void dfs(int u,int fa){
    in[u]=++tim;
    for(int v:g[u]){
        if(v!=fa) dfs(v,u);
    }
    out[u]=tim;
}