【bzoj3730:震波】【动态树分治】

题意

给出一棵树&＃xff0c;点有点权&＃xff0c;每次询问距离一个点不超过$k$的点的点权和&＃xff0c;或者修改一个点的点权&＃xff0c;强制在线。
$n\le 100000$

分析

把点分树建出来&＃xff0c;然后对每个分治中心用树状数组维护到该点距离为定值的点权和&＃xff0c;以及到他点分树上父亲距离为定值的点权和。查询的时候每次沿着父亲往上跳&＃xff0c;在计算当前点贡献时需要减去上一个点所在子树的贡献。
时间复杂度O(nlog⁡2n)O(n\log^2n)O(nlog2n)

代码

#include
#include
#include
#include
#include
#includeconst int N&＃61;100005;int n,m,cnt,last[N],dep[N],dfn[N],top,rmq[N*2][20],lg[N*2],bin[20],c1[20][N],c2[20][N],fa[N],rt,sum,mx[N],a[N],beg[N],size[N],dd[N],tot[20],end[N];
bool vis[N];
struct edge{int to,next;}e[N*2];void addedge(int u,int v)
{e[&＃43;&＃43;cnt].to&＃61;v;e[cnt].next&＃61;last[u];last[u]&＃61;cnt;e[&＃43;&＃43;cnt].to&＃61;u;e[cnt].next&＃61;last[v];last[v]&＃61;cnt;
}void dfs(int x,int fa)
{rmq[&＃43;&＃43;top][0]&＃61;x;dep[x]&＃61;dep[fa]&＃43;1;dfn[x]&＃61;top;for (int i&＃61;last[x];i;i&＃61;e[i].next)if (e[i].to!&＃61;fa) dfs(e[i].to,x),rmq[&＃43;&＃43;top][0]&＃61;x;
}void get_rmq()
{for (int i&＃61;1;i<&＃61;top;i&＃43;&＃43;) lg[i]&＃61;log(i)/log(2);bin[0]&＃61;1;for (int i&＃61;1;i<&＃61;lg[top];i&＃43;&＃43;) bin[i]&＃61;bin[i-1]*2;for (int j&＃61;1;j<&＃61;lg[top];j&＃43;&＃43;)for (int i&＃61;1;i&＃43;bin[j]-1<&＃61;top;i&＃43;&＃43;)rmq[i][j]&＃61;dep[rmq[i][j-1]]<dep[rmq[i&＃43;bin[j-1]][j-1]]?rmq[i][j-1]:rmq[i&＃43;bin[j-1]][j-1];
}int get_dis(int x,int y)
{int l&＃61;std::min(dfn[x],dfn[y]),r&＃61;std::max(dfn[x],dfn[y]),w&＃61;lg[r-l&＃43;1];return dep[x]&＃43;dep[y]-2*std::min(dep[rmq[l][w]],dep[rmq[r-bin[w]&＃43;1][w]]);
}void get_root(int x,int fa)
{size[x]&＃61;1;mx[x]&＃61;0;for (int i&＃61;last[x];i;i&＃61;e[i].next){if (e[i].to&＃61;&＃61;fa||vis[e[i].to]) continue;get_root(e[i].to,x);size[x]&＃43;&＃61;size[e[i].to];mx[x]&＃61;std::max(mx[x],size[e[i].to]);}mx[x]&＃61;std::max(mx[x],sum-size[x]);if (!rt||mx[x]<mx[rt]) rt&＃61;x;
}void ins1(int d,int x,int y)
{while (x<&＃61;n) c1[d][x]&＃43;&＃61;y,x&＃43;&＃61;x&(-x);
}void ins2(int d,int x,int y)
{while (x<&＃61;n) c2[d][x]&＃43;&＃61;y,x&＃43;&＃61;x&(-x);
}int query1(int d,int x)
{if (!d) return 0;int ans&＃61;0;while (x) ans&＃43;&＃61;c1[d][x],x-&＃61;x&(-x);return ans;
}int query2(int d,int x)
{if (!d) return 0;int ans&＃61;0;while (x) ans&＃43;&＃61;c2[d][x],x-&＃61;x&(-x);return ans;
}void pre(int x,int fa,int p1,int p2)
{ins1(dd[p1],beg[p1]&＃43;get_dis(p1,x),a[x]);if (p2) ins2(dd[p1],beg[p1]&＃43;get_dis(p2,x)-1,a[x]);tot[dd[p1]]&＃43;&＃43;;size[x]&＃61;1;for (int i&＃61;last[x];i;i&＃61;e[i].next)if (e[i].to!&＃61;fa&&!vis[e[i].to]) pre(e[i].to,x,p1,p2),size[x]&＃43;&＃61;size[e[i].to];
}void solve(int x)
{vis[x]&＃61;1;dd[x]&＃61;dd[fa[x]]&＃43;1;beg[x]&＃61;tot[dd[x]]&＃43;1;pre(x,0,x,fa[x]);end[x]&＃61;tot[dd[x]];for (int i&＃61;last[x];i;i&＃61;e[i].next)if (!vis[e[i].to]){rt&＃61;0;sum&＃61;size[e[i].to];get_root(e[i].to,x);fa[rt]&＃61;x;solve(rt);}
}int query(int x,int y)
{int ans&＃61;0,ls&＃61;0,now&＃61;x;while (now){int d&＃61;y-get_dis(x,now);if (d>&＃61;0) ans&＃43;&＃61;query1(dd[now],std::min(beg[now]&＃43;d,end[now]))-query1(dd[now],beg[now]-1);if (d>&＃61;0) ans-&＃61;query2(dd[ls],std::min(beg[ls]&＃43;d-1,end[ls]))-query2(dd[ls],beg[ls]-1);ls&＃61;now;now&＃61;fa[now];}return ans;
}void modify(int x,int y)
{int del&＃61;y-a[x],now&＃61;x;a[x]&＃61;y;while (now){ins1(dd[now],beg[now]&＃43;get_dis(now,x),del);if (fa[now]) ins2(dd[now],beg[now]&＃43;get_dis(fa[now],x)-1,del);now&＃61;fa[now];}
}int main()
{scanf("%d%d",&n,&m);for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) scanf("%d",&a[i]);for (int i&＃61;1;i<n;i&＃43;&＃43;){int x,y;scanf("%d%d",&x,&y);addedge(x,y);}dfs(1,0);get_rmq();rt&＃61;0;sum&＃61;n;get_root(1,0);solve(rt);int ans&＃61;0;while (m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);x^&＃61;ans;y^&＃61;ans;if (!op) printf("%d\n",ans&＃61;query(x,y));else modify(x,y);}return 0;
}