description
solution
动态点分治第二题。
动态维护带权重心和动态查询(sum_i dist(u,i))。
查询开一堆数组在点分树上修改就行。
找带权重心的时候从根节点开始找
每次判断的时候点分树暴力往孩子跳求答案
需要注意的是:
在点分树上往重心所在的子树跳的时候,
分重心的答案不一定比当前重心的答案优
因此我们只能往当前重心的一个连通块移动一步
凭借这个判断
而不是拿分重心和当前重心的值来判断
因为找带权重心出错的原因至少重写了2遍
我还是太弱了
code
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#define RG register
#define il inline
using namespace std;
typedef long long ll;
typedef double dd;
const int N=1e5+10;
const int mod=1e9+7;
const int inf=2147483647;
const ll INF=1ll<<60;
il ll read(){
RG ll d=0,w=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')d=d*10+ch-48,ch=getchar();
return d*w;
}
il void file(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int n,q;
int head[N],nxt[N<<1],to[N<<1],val[N<<1],cnt;
il void add(int u,int v,int w){
to[++cnt]=v;
val[cnt]=w;
nxt[cnt]=head[u];
head[u]=cnt;
}
/*********************************************************************/
int pa[N],siz[N],son[N],top[N],deb[N],dep[N];
void dfs1(int u,int ff){
pa[u]=ff;siz[u]=1;son[u]=0;deb[u]=deb[ff]+1;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==ff)continue;
dep[v]=dep[u]+val[i];dfs1(v,u);siz[u]+=siz[v];
if(!son[u]||siz[son[u]]<siz[v])son[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp;
if(son[u])dfs2(son[u],tp);
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==son[u]||v==pa[u])continue;
dfs2(v,v);
}
}
il int lca(int u,int v){
while(top[u]!=top[v]){
if(deb[top[u]]<deb[top[v]])swap(u,v);
u=pa[top[u]];
}
return deb[u]<deb[v]?u:v;
}
il int dist(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
/*********************************************************************/
int dhead[N],dnxt[N],dto[N],drt[N],dcnt;
il void dadd(int u,int v,int rt){
dto[++dcnt]=v;
dnxt[dcnt]=dhead[u];
drt[dcnt]=rt;
dhead[u]=dcnt;
}
int rt,block,w[N],sz[N],fa[N];bool vis[N];
void getrt(int u,int ff){
sz[u]=1;w[u]=1;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==ff||vis[v])continue;
getrt(v,u);sz[u]+=sz[v];
w[u]=max(w[u],sz[v]);
}
w[u]=max(w[u],block-sz[u]);
if(w[rt]>w[u])rt=u;
}
void solve(int u,int ff){
fa[u]=ff;vis[u]=1;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==ff||vis[v])continue;
block=sz[v];rt=0;
getrt(v,0);
dadd(u,v,rt);
solve(rt,u);
}
}
/*********************************************************************/
int RT;
ll sum[N],tofa[N],gather[N];
il void modify(int u,int e){
for(RG int x=u;x;x=fa[x]){
sum[x]+=e;
gather[x]+=1ll*dist(u,x)*e;
if(fa[x])tofa[x]+=1ll*dist(u,fa[x])*e;
}
}
il ll count(int u){
RG ll ret=gather[u];
for(RG int x=u;fa[x];x=fa[x])
ret+=(gather[fa[x]]-tofa[x])+1ll*dist(fa[x],u)*(sum[fa[x]]-sum[x]);
return ret;
}
il ll query(){
RG int u=RT,b=0;ll now,ret;
while(2333){
b=0;now=count(u);
for(RG int i=dhead[u];i;i=dnxt[i]){
RG int v=dto[i];ret=count(v);
if(ret<now){now=ret;b=1;u=drt[i];break;}
}
if(!b)return now;
}
}
/*********************************************************************/
int main()
{
n=read();q=read();
for(RG int i=1,u,v,wl;i<n;i++){
u=read();v=read();wl=read();
add(u,v,wl);add(v,u,wl);
}
dfs1(1,0);dfs2(1,1);
block=w[0]=n;rt=0;
getrt(1,0);RT=rt;
solve(rt,0);
for(RG int i=1,u,e;i<=q;i++){
u=read();e=read();modify(u,e);
printf("%lld
",query());
}
return 0;
}