bzoj 3924
動態點分治好題
首先我們考慮一個暴力做法：
每次修改之后選一個點作為根搜索整棵樹，然后換根dp即可
考慮每次換根時，移向的點的消耗會減少子樹代價之和*邊權，而其余部分代價會增加剩余代價*邊權
這樣每次換根都是$O(1)$的，總時間復雜度$O(nm)$，可以通過...20分！
貼代碼：
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> #define ll long long using namespace std; int n,m; struct Edge { int next; int to; int val; }edge[10005]; int head[5005]; ll num[5005]; int son[5005]; int cnt=1; int s=0; void init() { memset(head,-1,sizeof(head)); cnt=1; } void add(int l,int r,int w) { edge[cnt].next=head[l]; edge[cnt].to=r; edge[cnt].val=w; head[l]=cnt++; } ll ans=0; void dfs1(int x,int fx,ll d) { ans+=(ll)(num[x]*d); son[x]+=num[x]; for(int i=head[x];i!=-1;i=edge[i].next) { int to=edge[i].to; if(to==fx) { continue; } dfs1(to,x,(ll)d+edge[i].val); son[x]+=son[to]; } } void dfs2(int x,int fx,ll tot) { for(int i=head[x];i!=-1;i=edge[i].next) { int to=edge[i].to; if(to==fx) { continue; } ans=min(ans,(ll)tot+(ll)(s-2*son[to])*edge[i].val); dfs2(to,x,tot+(ll)(s-2*son[to])*edge[i].val); } } int main() { scanf("%d%d",&n,&m); init(); for(int i=1;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); num[x]+=y; s+=y; ans=0; memset(son,0,sizeof(son)); dfs1(1,1,0); dfs2(1,1,ans); printf("%lld\n",ans); } return 0; }
然后我們考慮正解
我們發現：這個換根的過程有兩個可以優化的地方：
首先，并不是所有點都可能作為根的，有一些點顯然不會作為根，而這一部分其實應該剪掉！
第二：每次修改只是重構了這棵樹一條樹鏈上的信息，因此我們每次修改就重新搜索整棵樹是不合算的
因此我們就可以考慮用點分治來優化這個過程了
當然了，由于涉及修改，所以肯定是動態點分治
用上點分治之后，第一點可以用類似這道題的方法來解決，即向各個方向走，找一個最優的方向去走即可
第二點就可以直接在點分樹上暴力走了，這樣就結束了
然后我們可以考慮如何修改和查詢了
對每個節點維護三個值，分別維護自己子樹內的權值，自己子樹內的總權值貢獻和自己子樹中權值對父節點的貢獻
注意區分權值與權值貢獻：權值貢獻考慮邊權！
修改的時候直接暴力修改即可
假設我們想查詢以某個點為根的貢獻，那么我們就需要統計兩部分：一部分是自己子樹內的，另一部分是自己子樹外的
自己子樹內的可以直接加
自己子樹外的我們可以沿著點分樹向上跳，跳到的每個節點在子樹中要去掉來源點那部分子樹的貢獻，然后加上當前點的權值貢獻即可
然后每次查詢的時候先任意指定一個點然后向四周走，如果走到的點比當前點更優那么就向那個方向走
有個小trick：在點分樹上每個點深度都是對數級別，因此我們可以直接預處理出每個節點與它的幾層父親的距離，查詢時直接調用就可以了
貼代碼：
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> using namespace std; typedef long long ll; struct Edge { int nxt,to; ll val; }edge[200005]; int head[100005]; int pre[100005]; ll dis[100005]; int dep[100005],soz[100005],son[100005]; int siz[100005],maxp[100005]; int vis[100005],ttop[100005],f[100005]; ll w1[100005],w2[100005],w3[100005]; ll d[100005][25]; int rt,s,rot; int n,m; int cnt=1; void add(int l,int r,ll w) { edge[cnt].nxt=head[l]; edge[cnt].to=r; edge[cnt].val=w; head[l]=cnt++; } void get_rt(int x,int fx) { siz[x]=1,maxp[x]=0; for(int i=head[x];i;i=edge[i].nxt) { int to=edge[i].to; if(to==fx||vis[to])continue; get_rt(to,x); siz[x]+=siz[to],maxp[x]=max(maxp[x],siz[to]); } maxp[x]=max(maxp[x],s-siz[x]); if(maxp[x]<maxp[rt])rt=x; } void solve(int x) { vis[x]=1; for(int i=head[x];i;i=edge[i].nxt) { int to=edge[i].to; if(vis[to])continue; rt=0,s=siz[to]; get_rt(to,x); pre[rt]=x,solve(rt); } } void dfs(int x,int fx,int deep) { soz[x]=1,dis[x]=deep,dep[x]=dep[fx]+1,f[x]=fx; for(int i=head[x];i;i=edge[i].nxt) { int to=edge[i].to; if(to==fx)continue; dfs(to,x,deep+edge[i].val); soz[x]+=soz[to],son[x]=(soz[son[x]]<soz[to])?to:son[x]; } } void redfs(int x,int topx,int fx) { ttop[x]=topx; if(son[x])redfs(son[x],topx,x); for(int i=head[x];i;i=edge[i].nxt) { int to=edge[i].to; if(to==fx||to==son[x])continue; redfs(to,to,x); } } int LCA(int x,int y) { while(ttop[x]!=ttop[y]) { if(dep[ttop[x]]<dep[ttop[y]])swap(x,y); x=f[ttop[x]]; } return dep[x]<dep[y]?x:y; } ll get_dis(int x,int y) { return dis[x]+dis[y]-2*dis[LCA(x,y)]; } void update(int x,ll v) { for(int i=x,j=0,k=0;i;j=i,i=pre[i],k++) { ll temp=d[x][k]*v; w1[i]+=temp,w3[i]+=v; if(j)w2[j]+=temp; } } ll query(int x) { ll ret=0; for(int i=x,j=0,k=0;i;j=i,i=pre[i],k++)ret+=w1[i]-w2[j]+(w3[i]-w3[j])*d[x][k]; return ret; } int divi(int x) { ll ori=query(x); int ret=-1; for(int i=head[x];i;i=edge[i].nxt) { int to=edge[i].to; ll temp=query(to); if(temp<ori)ret=to,ori=temp; } return ret; } template <typename T>inline void read(T &x) { T f=1,c=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x=c*f; } int main() { read(n),read(m); for(int i=1;i<n;i++) { int x,y; ll z; read(x),read(y),read(z); add(x,y,z),add(y,x,z); } dfs(1,1,0),redfs(1,1,1); rt=0,maxp[0]=0x3f3f3f3f,s=n; get_rt(1,0),rot=rt,solve(rt); for(int i=1;i<=n;i++)for(int k=1,j=pre[i];j;k++,j=pre[j])d[i][k]=get_dis(i,j); int x;ll va; read(x),read(va),m--; update(x,va),printf("0\n"); while(m--) { read(x),read(va); update(x,va); int ans=rot; int t=divi(rot); while(t!=-1)ans=t,t=divi(t); printf("%lld\n",query(ans)); } return 0; }
浙公網安備 33010602011771號