[BZOJ3924][Zjoi2015][點分樹][暴力]幻想鄉戰略游戲

2019-11-11 06:50:26

字體：大中小

來源：轉載

供稿：網友

年前的坑今天補……

題意

求一棵樹的帶權重心，支持修改權值。

動態樹分治，也叫點分樹。就是把每層的重心連成一棵樹，然后在這棵樹上亂搞（具體網上教程多）。

不過第一次寫這題暴力碾過去了…..好像還挺快的….

先講暴力假設上一次找到的重心在u,那么如果在某一點v增加了權值，那當前的重心一定是在u到v的相反方向上，只要沿著相反方向找就行了。

具體怎么找…可以這么想：當前結點為x，y為與x相鄰的結點，w[x]為x結點上的權值，cnt為總權值，那么如果cnt-w[y]< w[y]即cnt<2*w[y]時，往y點移動，直到不能移動為止。至于為什么……自己腦補一下

w[x]可以用dfs序加BIT維護。

#include <cstdio>#include <iostream>#include <string>#include <cstring>#define inf 1ll<<60#define N 100010using namespace std;typedef long long ll;int G[N],n,m,tt,rt,l[N],r[N],tc,lcA[N][25],dp[N];ll B[N<<1],Ans,A[N],tot,ds[N];struct edge{ int w,t,nx;}E[N<<1];struct lef{ int f,w,d;}T[N];inline char C(){ static char buf[100000],*p1=buf,*p2=buf; if(p1==p2){ p2=(p1=buf)+fread(buf,1,100000,stdin); if(p1==p2) return EOF; } return *p1++;}inline void reaD(int &x){ char Ch=C();x=0;int f=1; for(;Ch>'9'||Ch<'0';Ch=C())if(Ch=='-')f=-1; for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=C());x*=f;}inline void reaD(ll &x){ char Ch=C();x=0;ll f=1; for(;Ch>'9'||Ch<'0';Ch=C())if(Ch=='-')f=-1; for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=C());x*=f;}inline void InserT(int x,int y,int w){ E[++tt].t=y;E[tt].nx=G[x];E[tt].w=w;G[x]=tt; E[++tt].t=x;E[tt].nx=G[y];E[tt].w=w;G[y]=tt;}inline void build(int g,int f,int d){ T[g].f=f;l[g]=++tc;T[g].d=d; dp[g]=dp[f]+1;ds[g]=ds[f]+d; lcA[g][0]=f; for(int i=1;i<=20;i++) lcA[g][i]=lcA[lcA[g][i-1]][i-1]; for(int i=G[g];i;i=E[i].nx) if(E[i].t!=f) build(E[i].t,g,E[i].w); r[g]=++tc;}inline void add(int x,int y){ for(;x<=tc;x+=x&-x) B[x]+=y;}inline ll query(int x){ ll res=0; for(;x;x-=x&-x) res+=B[x]; return res;}inline ll Qlw(int x){ return query(r[x])-query(l[x]);}int w[30],wt;inline void Pt(ll x){ if(!x){putchar(48);putchar('/n');return;} if(x<0){putchar('-');x=-x;}; while(x)w[++wt]=x%10,x/=10; for(;wt;wt--)putchar(48+w[wt]);putchar('/n');}inline void swap(int &x,int &y){ int z=x;x=y;y=z;}inline int clca(int x,int y){ if(dp[x]<dp[y]) swap(x,y); int delt=dp[x]-dp[y],i; for(i=0;i<=20;i++) if(delt&(1<<i)) x=lcA[x][i]; while(x!=y){ for(i=-1;i;i++) if(lcA[x][i+1]==lcA[y][i+1]) break; if(i==-1) return lcA[x][0]; x=lcA[x][i];y=lcA[y][i]; } return x;}int main(){ freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); reaD(n);reaD(m); for(int i=1,x,y,w;i<n;i++)reaD(x),reaD(y),reaD(w),InserT(x,y,w); /*int ok=0; for(int i=1;i<=n;i++) if(du[i]>2){ok=1;break;} if(!ok){linktime();return 0;}*/ build(1,0,0);reaD(rt); reaD(A[rt]);tot+=A[rt]; add(r[rt],A[rt]); Pt(Ans=0); for(int i=1,x,y,j,lca;i<m;i++){ reaD(x);reaD(y); add(r[x],y);A[x]+=y;tot+=y; lca=clca(x,rt);Ans+=1ll*(ds[x]+ds[rt]-2*ds[lca])*y; //S(rt,0,Ans); while(1){ if(T[rt].f&&tot>2ll*Qlw(rt)){Ans-=1ll*(tot-2*Qlw(rt))*T[rt].d;rt=T[rt].f;continue;} for(j=G[rt];j;j=E[j].nx) if(T[rt].f!=E[j].t&&tot<2ll*Qlw(E[j].t)){ Ans-=1ll*(2*Qlw(E[j].t)-tot)*E[j].w; rt=E[j].t; break; } if(!j) break; } Pt(Ans); } return 0;}

復雜度是O(λnlogn) $O(/lambda nlogn)$ ,λ $/lambda$ 為一個常數（由數據決定），由于隨機數據，所以λ $/lambda$ 較小，所以復雜度竟然比標算小……

正確做法是點分樹。建出點分樹，每次找只要從根節點開始分治地找就行了。

復雜度O(nlog2n) $O(nlog^2n)$

#include <cstdio>#define N 100010typedef long long ll;int n,m,maxs,root,sizz,trot;ll Anst,Ans,nAns;int nG[N],G[N],cnt,V[N],p[N],dfslt[N<<2],lca[N<<2][20],dept[N],pst[N],tw[N<<2],ben[N];ll w[N],dist[N],subd[N],dis2[N];struct edge{ int t,nx,t1; ll w;}nE[N<<2],E[N<<2];inline char C(){ static char buf[100000],*p1=buf,*p2=buf; if(p1==p2){ p2=(p1=buf)+fread(buf,1,100000,stdin); if(p1==p2) return EOF; } return *p1++;}inline void reaD(int &x){ char Ch=C();x=0;int f=1; for(;Ch>'9'||Ch<'0';Ch=C())if(Ch=='-')f=-1; for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=C());x*=f;}inline void InsEdge(int u,int v,int w){ nE[++cnt].t=v;nE[cnt].nx=nG[u];nE[cnt].w=w;nG[u]=cnt; nE[++cnt].t=u;nE[cnt].nx=nG[v];nE[cnt].w=w;nG[v]=cnt;}inline int max(const int &a,const int &b){ return a<b?b:a;}void Getsz(int x,int f){ sizz++; for(int i=nG[x];i;i=nE[i].nx) if(!V[nE[i].t]&&nE[i].t!=f) Getsz(nE[i].t,x);}int GetRoot(int x,int f){ int mx=0,sz=1,nsz; for(int i=nG[x];i;i=nE[i].nx){ int t=nE[i].t; if(V[t]||t==f) continue; nsz=GetRoot(t,x); mx=max(mx,nsz); sz+=nsz; } mx=max(mx,sizz-sz); if(mx<maxs) maxs=mx,root=x; return sz;}inline void AddEdge(int x,int y,int z){ E[++cnt].t=y;E[cnt].nx=G[x];E[cnt].t1=z;G[x]=cnt;}void swap(int &x,int &y){ int z=x;x=y;y=z;}int LCA(int x,int y){ int a=pst[x],b=pst[y]; if(a>b) swap(a,b); int t=tw[b-a+1]; return dept[lca[a][t]]<dept[lca[b-(1<<t)+1][t]]?lca[a][t]:lca[b-(1<<t)+1][t];}int divont(int x,int f){ sizz=0,maxs=1<<30,Getsz(x,0),GetRoot(x,0); int nRoot=root,nxRoot;V[nRoot]=1;p[nRoot]=f; for(int i=nG[nRoot];i;i=nE[i].nx) if(nE[i].t!=f&&!V[nE[i].t]){ nxRoot=divont(nE[i].t,nRoot); AddEdge(nRoot,nxRoot,nE[i].t); } return nRoot;}void dfs(int x,int f){ dept[x]=dept[f]+1;dfslt[pst[x]=++cnt]=x; for(int i=nG[x];i;i=nE[i].nx) if(nE[i].t!=f)dist[nE[i].t]=dist[x]+nE[i].w,dfs(nE[i].t,x),dfslt[++cnt]=x;}void PRelca(){ for(int i=1;i<=cnt;i++) tw[i]=tw[i-1]+((1<<tw[i-1]+1)==i); for(int i=1;i<=cnt;i++) lca[i][0]=dfslt[i]; for(int k=1;k<=tw[cnt];k++) for(int i=1;i+(1<<k)-1<=cnt;i++) lca[i][k]=dept[lca[i][k-1]]<dept[lca[i+(1<<k-1)][k-1]]?lca[i][k-1]:lca[i+(1<<k-1)][k-1];}ll dis(int x,int y){ return dist[x]+dist[y]-2*dist[LCA(x,y)];}inline void Addtr(int x,int y){ w[x]+=y; for(int i=x,j;p[i];i=p[i]){ w[p[i]]+=y; subd[p[i]]+=dis(x,p[i])*y; dis2[i]+=dis(x,p[i])*y; }}inline ll min(const ll &a,const ll &b){ return a<b?a:b;}inline ll disf(int x){ ll re=subd[x]; for(int i=x;p[i];i=p[i]){ ll disr=dis(x,p[i]); re+=subd[p[i]]-dis2[i]; re+=(w[p[i]]-w[i])*disr; } return re;}inline ll query(int x){ bool flg=1; ll tot=disf(x); for(int i=G[x];i;i=E[i].nx){ ll cost=disf(E[i].t1); if(cost<tot) return query(E[i].t); } return tot;}int main(){ freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); reaD(n);reaD(m); for(int i=1,u,v,w;i<n;i++)reaD(u),reaD(v),reaD(w),InsEdge(u,v,w); cnt=0,dfs(1,0),Prelca(), cnt=0,trot=divont(1,0),cnt=0; for(int i=1;i<=m;i++){ int x,y; reaD(x);reaD(y); Ans=(Anst+=y*dis(x,trot)); Addtr(x,y),cnt+=y; printf("%lld/n",query(trot)); }}

事實證明如果考場上想不出標算或沒時間寫標算，這種信仰暴力還是可以接受的……

上一篇：123. Best Time to Buy and Sell Stock III（同小米風口的豬）

下一篇：centos7安裝scala