今天一整天都感觉有点心神不定。
这题我的写法是跟kczno1大爷的写法一样。
然后觉得点分治复杂度跟度数有关,是不对的。那标算还点分治?
在洛谷上AC后,又在bzoj上交了一发,好像是rk10?
接着就发现原版题面里有一句话“每个点的度数不超过20”,真想**出题人。
#include#include #include typedef long long ll; const int L=3000000,N=100005; char ibuf[L],*ih=ibuf,obuf[L],*oh=obuf; inline int getint(){ register int x=0,f=1; while(!isdigit(*ih))if(*ih++=='-')f=-1; for(;isdigit(*ih);)x=x*10+(*ih++^48); return x*f; } inline void putl(register ll x){ static int buf[30],xb; if(x){ for(xb=0;x;x/=10)buf[++xb]=x%10; for(;xb;)*oh++=buf[xb--]|48; }else *oh++='0'; } int n,a,b,c,q,i; struct tree{ struct edge{ int to,next,w; }e[N<<1]; int h[N],xb,sz[N],dep[N],dad[N],dfn[N],id[N],top[N],ma[N],v[N],sv; ll dv; struct segtree{ struct node{ int l,r,mid,add,x; ll s; std::pair m; }t[N<<2]; inline void Add(int i,int v){ t[i].add+=v,t[i].s+=1ll*v*t[i].x; t[i].m.first+=v; } inline void pushdown(int i){ if(t[i].add){ Add(i<<1,t[i].add); Add(i<<1|1,t[i].add); t[i].add=0; } } void build(int i,int l,int r,int*dep,int*dad,int*dfn){ t[i].l=l,t[i].r=r,t[i].mid=(l+r)>>1;t[i].m.second=r; if(l==r){t[i].x=dep[dfn[l]]-dep[dad[dfn[l]]];return;} build(i<<1,l,t[i].mid,dep,dad,dfn),build(i<<1|1,t[i].mid+1,r,dep,dad,dfn); t[i].x=t[i<<1].x+t[i<<1|1].x; }; void add(int i,int l,int r,int v){ if(t[i].l==l && t[i].r==r){Add(i,v);return;} pushdown(i); if(l>t[i].mid)add(i<<1|1,l,r,v); else if(r<=t[i].mid)add(i<<1,l,r,v); else add(i<<1,l,t[i].mid,v),add(i<<1|1,t[i].mid+1,r,v); t[i].s=t[i<<1].s+t[i<<1|1].s; t[i].m=t[i<<1].m.first>t[i<<1|1].m.first?t[i<<1].m:t[i<<1|1].m; } ll query(int i,int l,int r){ if(t[i].l==l && t[i].r==r)return t[i].s; pushdown(i); if(t[i].mid =sv); return t[i].m.second; } }t; inline void addedge(int u,int v,int w){ e[++xb]=(edge){v,h[u],w};h[u]=xb; e[++xb]=(edge){u,h[v],w};h[v]=xb; } void dfs1(int x,int fa){sz[x]=1;dad[x]=fa; for(int i=h[x];i;i=e[i].next)if(e[i].to!=fa){ dep[e[i].to]=dep[x]+e[i].w;dfs1(e[i].to,x);sz[x]+=sz[e[i].to]; if(sz[e[i].to]>sz[ma[x]])ma[x]=e[i].to; } } void dfs2(int x,int fa){ dfn[id[x]=++xb]=x; if(!ma[x])return; top[ma[x]]=top[x];dfs2(ma[x],x); for(int i=h[x];i;i=e[i].next)if(e[i].to!=fa && e[i].to!=ma[x])top[e[i].to]=e[i].to,dfs2(e[i].to,x); } inline void prepare(){ dfs1(1,0);xb=0;top[1]=1; dfs2(1,0); t.build(1,1,n,dep,dad,dfn); } inline void add(int x,int v){ for(sv+=v,dv+=1ll*dep[x]*v;x;x=dad[top[x]]) t.add(1,id[top[x]],id[x],v); } inline ll query(){ static int x;register ll ans; for(x=dfn[t.query2(sv)],ans=dv+1ll*dep[x]*sv;x;x=dad[top[x]]) ans-=t.query(1,id[top[x]],id[x])<<1; return ans; } }t; int main(){ fread(ibuf,1,L,stdin);n=getint(),q=getint(); for(i=1;i