HLD 树链剖分

应用于树形数据结构上进行优化的查询和更新操作

快速查询或修改，O(logn)

可能求的：最大、最小、和、路径更新

重（zhong）节点：每个链都是从某节点开始到子树中的一个重节点的路径。

'轻''重'实际上是用来形容【边】的，不是节点。

如果一条边记录为重，那么才能进行相连。

如果只有一个点，那它本身也是一条链。

进行树链剖分：

   1、构建链：遍历树结构，为各个边标记"重"或"轻"。通过DFS完成，每个节点至多有一条重链，可以有多条轻链。

   2、预处理：为了加速查询或修改，需要使用线段树等手段对每个链进行预处理，这样单次的查询或修改时间复杂度就是O(logn)

   3、执行查询、更新操作。

前提是要先存好一棵树

1、dfshld() 分出轻重

2、dfspos() 节点定位

//结构体建链

struct edge{

   int to;

   int next;

   int weight=1;

};

struct node{

   int depth;

   int heavy;//重量

   int heavychild;

   int listid;//记录存放的重链id

   vector<edge> es;

} nodes[MAXN];

int N;

void addEdge(int u,int v,int w=1){

   nodes[u].es.push_back({v,nodes[u].es.size(),w});

   nodes[v].es.push_back({u,nodes[v].es.size(),w});

}

int main(){

   cin>>N>>R;

   for(int i=1;i<N;i++){

       int u,v,w;//

       cin>>u>>v;

       addEdge(u,v);

   }

   dfsHLD1(R,0);//从根节点开始，求重量

   dfsHLD2(R);//从根节点开始，找重链

   通过listed遍历各个链

}

int dfsHLD1(int root,int depth){

   nodes[root].depth=depth;

   int maxhe=0;

   nodes[root].heavy=1;

   for(auto &e:nodes[root].es){

       int child=e.to;

       nodes[root].heavy+=dfsHLD(child,depth+1);

   }

}

int listid=1;

void dfsHLD2(int root){

   nodes[root].listid=listid++;

   nodes[root].heavychild=0;

   int k=0;

   for(auto &e:nodes[root].es){

       int child=e.to;

       if(k<nodes[child].heavy){

           k=nodes[child].heavy;

           nodes[root].heavychild=child;

       }

   }

   for(auto &e:nodes[root].es){

       int child=e.to;

       if(child!=nodes[root].heavychild)

           dfsHLD2(child);

   }

}