长链剖分模板

解决的是某一结点对应子树深度为k的结点的某些信息(如和) 与dsu on tree的不同：
    1.L[](id[])数组含义仍不变，但R[]数组保存的是长链的最后一个结点对应的dfn
    (不再是子树最后一个结点对应的dfn)，son[u]保存的是u对应链最长儿子的编号 
    2.不同长链的L,R都是没有任何交集的，也就是说它们用于统计的数据结构是独立的，而不像dsu on tree一样是公用的，故在dsu中处理轻重儿子的顺序就无关紧要了，可以先处理重儿子，再处理轻儿子。

#include 

typedef long long ll;
using namespace std;

const int N=1e5+10;
int h[N],to[2*N],ne[2*N],cnt;
int dep[N],fa[N],son[N],len[N];
//用len数组用于保存长链的长度 
int top[N],dfn,L[N],R[N],idx[N],skp;
long long val[N],ans[N],sum[N];
int n,m;
vector >lis[N];
void add_edge(int u,int v){
	to[cnt]=v;
	ne[cnt]=h[u];
	h[u]=cnt++;
} 
void init(){
	cnt=0;
	memset(h,-1,sizeof(h));
}
void dfs1(int u,int fat){
	dep[u]=dep[fat]+1;
	fa[u]=fat;
	for(int i=h[u];i!=-1;i=ne[i]){
		if(to[i]!=fat)
			dfs1(to[i],u);
		if(!son[u]||len[son[u]]