Update：这种分块写法...可以被卡掉啊...
好像没有靠谱的树分块写法.../*对树上节点进行分块，每个点记录dep,fa,val,Max,Sum，Max,Sum表示当前点在该块内的子树中权值最大值与和 节点i各值表示从root[i]到i一段路径的的对应值。因为求值时应是向上找到LCA，所以记录一个从根到叶的信息 修改一个点i时影响的只是该块内从fa[i]以下的点，暴力向下更新 查询路径时不断向上找LCA。注意每次都是让深度大的跳，以避免分类讨论 当两个点在一个块内时暴力一步步向上 直到LCA 存两组边，一是原图中的边，二是每个块内的关系边 */#include#include #include #include #define gc() getchar()const int N=3e4+5,INF=0x3f3f3f3f;int n,limit,val[N],rt[N],dep[N],fa[N],Max[N],Sum[N],Enum,H[N],nxt[N<<1],to[N<<1];inline int read(){ int now=0,f=1;register char c=gc(); for(;!isdigit(c);c=gc()) if(c=='-') f=-1; for(;isdigit(c);now=now*10+c-'0',c=gc()); return now*f;}void AddEdge(int u,int v){ to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum; to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;}void Build(int x,int &res){ if(res) rt[x]=rt[fa[x]],--res; else rt[x]=x,res=limit; for(int i=H[x];i;i=nxt[i]) if(to[i]!=fa[x]) dep[to[i]]=dep[x]+1,fa[to[i]]=x,Build(to[i],res);}void Update(int x,int Mx,int Sm){ Sm+=val[x], Sum[x]=Sm; Mx=std::max(Mx,val[x]), Max[x]=Mx; for(int i=H[x];i;i=nxt[i]) if(rt[x]==rt[to[i]] && to[i]!=fa[x]) Update(to[i],Mx,Sm);}int Query(int x,int y,bool f){ int sm=0,mx=-INF; while(rt[x]!=rt[y])//不在同一块时直接用整块的信息 { if(dep[x]