樹與圖

• 如果真的在圖上跑算法，那么光建圖復雜度就$O(n^{2}logn)$了，這顯然不可行。所以一定要把 在圖上的操作 轉換成 在樹上的操作
• 在圖上刪去點u，相當于在樹上刪去u到根節(jié)點的鏈，并把u的整棵子樹刪掉
• 如果我們枚舉算法可能產生的所有過程，然后再去求每個過程對應的刪點次數(shù)，那么光枚舉過程就已經可以T爆了
• 所以我們只能枚舉刪點次數(shù)，然后求出該刪掉次數(shù)對應多少種過程
• 這可以用樹形DP實現(xiàn)，時間復雜度$O(n^3)$
• 可以想到用生成函數(shù)進一步優(yōu)化，即用次數(shù)來代表刪點次數(shù)，系數(shù)來代表可能過程種數(shù)，這樣合并兩棵子樹時直接用NTT把兩棵子樹的多項式乘起來即可
• 這樣會產生兩個問題：

代碼中每一步合并乘的$C_{j+k}^k$怎么辦？

NTT的時間復雜度是$O(nlogn)$$(這里n指多項式的最高次數(shù))$，這樣總時間復雜度就是$O(n^{3}logn)$，怎么還變大了？

就是這兩個問題讓我在考場上沒有繼續(xù)寫下去

• 對于第一個問題，我后來想到，其實不一定要在DP過程中乘$C_{j+k}^k$，DP完后再統(tǒng)一乘$（刪點次數(shù)）！$來定序也是可行的
• 對于第二個問題，在更新u時，直接用 分治NTT 把u的所有兒子上的多項式 一起 乘起來，不要那么傻逼想著用NTT一個接一個乘
  這樣時間復雜度降為$O(n^{2}lo{g}^{2}n)$，但還是會T
• 題目的時間復雜度很大程度上取決于NTT時多項式的最高次數(shù)，而多項式次數(shù)與刪點次數(shù)有關，所以考慮一下我們最多能刪幾個點
• 發(fā)現(xiàn)所選的要刪的點滿足如下規(guī)律：所選的任意兩個點都不互為祖先關系，且從根到每個葉子的路徑上都恰好有一個被選擇的點
• 即$u點的多項式的最高次數(shù)<=u子樹內葉節(jié)點的個數(shù)$，進一步地，因為每個節(jié)點的多項式最高次數(shù)至少為1，所以$u點的多項式最多是(u子樹內葉節(jié)點個數(shù))個多項式相乘的結果$
• 設$lea{f}_u$表示u的子樹中葉子的個數(shù)，則在u點分治NTT的時間總和$<=lea{f}_u(lo{g}^{2}lea{f}_u)$，整道題的總時間$<={\sum }_{u=1}^{n}lea{f}_u(lo{g}^{2}lea{f}_u)$
• 考慮兩種極端情況，一種是菊花圖，一種是一條很長的樹鏈，上面隨機的掛上一些類似菊花圖（深度小但點度數(shù)大）的子樹
• 按照上面的做法，菊花圖的時間復雜度可以做到$O(nlo{g}^{2}n)$，樹鏈的時間復雜度卻逼近$O(n^{2}lo{g}^{2}n)$
• 我們考慮給樹鏈換一種做法：
  枚舉在鏈上刪了哪個點，這樣一來整條鏈和被刪點的子樹都會被刪除，而被刪點上方的子樹不會被刪除，并且相互獨立了。
  因此，如果鏈上的點的多項式為$F_1(x),F_2(x),F_3(x)...$(按點深度由淺到深編號)，那么最后求出這條鏈的多項式為：$F_1(x)+F_1(x)F_2(x)+F_1(x)F_2(x)F_3(x)...$
  用分治NTT做，總時間$<=lea{f}_1(lo{g}^{2}lea{f}_1)$，所以時間復雜度為$O(nlo{g}^{2}n)$
• 考慮把這兩種做法結合起來，即對樹進行重鏈剖分，然后對每個節(jié)點的輕兒子分治NTT，對每條重鏈分治 NTT
• 具體來說，設$f_u(x)$表示u點的多項式
  深搜遍歷每個節(jié)點，假設當前遍歷到u
  若u為葉子節(jié)點：$f_u(x)=x$，返回
  若不是：執(zhí)行下述步驟
  ①若節(jié)點u有輕兒子：$f_u(x)={\prod }_{v\in lightson}{f}_v(x)$
  若沒有：$f_u(x)=1$
  ②若節(jié)點為重鏈端點：
  （設這條重鏈上的點由淺至深分別為$p_1,p_2,?,p_k$。顯然，$p_1$為鏈頭，$p_k$為葉子節(jié)點。）
  $f_{p_1}(x)=f_{p_1}(x)+f_{p_1}(x)f_{p_2}(x)+f_{p_1}(x)f_{p_2}(x)f_{p_3}(x)+...+f_{p_1}(x)f_{p_2}(x)f_{p_3}(x)...f_{p_{k?1}}+x$
  （$+x$是因為要考慮刪去自己的情況）
• 分析一下這樣做的時間復雜度，整道題的總時間$<={\sum }_{u\in top}lea{f}_u(lo{g}^{2}lea{f}_u)+{\sum }_{u=1}^n({\sum }_{v\in lightso{n}_u}lea{f}_v)[lo{g}^2({\sum }_{v\in lightso{n}_u}lea{f}_v)]$
• ${\sum }_{u\in top}lea{f}_u(lo{g}^{2}lea{f}_u)<={\sum }_{u\in top}lea{f}_u(lo{g}^{2}n)=lo{g}^{2}n{\sum }_{u\in top}lea{f}_u$ 。因為每個葉子節(jié)點到根節(jié)點的路徑上最多有$logn$條重鏈，而每個葉子節(jié)點又只在其到根節(jié)點的路徑上的重鏈頭處對${\sum }_{u\in top}lea{f}_u$有1的貢獻，所以${\sum }_{u\in top}lea{f}_u<=nlogn$，${\sum }_{u\in top}lea{f}_u(lo{g}^{2}lea{f}_u)<=nlo{g}^{3}n$
• ${\sum }_{u=1}^n({\sum }_{v\in lightso{n}_u}lea{f}_v)[lo{g}^2({\sum }_{v\in lightso{n}_u}lea{f}_v)]<={\sum }_{u=1}^n({\sum }_{v\in lightso{n}_u}lea{f}_v)(lo{g}^{2}n)=lo{g}^{2}n{\sum }_{u=1}^n({\sum }_{v\in lightso{n}_u}lea{f}_v)$ 。因為每個葉子節(jié)點到根節(jié)點的路徑上最多有$logn$條輕邊，即每個葉子節(jié)點最多只在$logn$個祖先處對${\sum }_{u=1}^n({\sum }_{v\in lightso{n}_u}lea{f}_v)$有1的貢獻，所以${\sum }_{u=1}^n({\sum }_{v\in lightso{n}_u}lea{f}_v)<=nlogn$，${\sum }_{u=1}^n({\sum }_{v\in lightso{n}_u}lea{f}_v)[lo{g}^2({\sum }_{v\in lightso{n}_u}lea{f}_v)]<=nlo{g}^{3}n$
• 因此總時間復雜度是$O(nlo{g}^{3}n)$，但由于樹剖$log$小和跑不滿等原因可以跑過

（最后樹剖分輕重兒子維護的處理類似這題，可以一起記憶）

#include<iostream> #include<cstdio> #include<vector> using namespace std; typedef long long ll; const int mod=998244353; const int N=100010; const int M=250000; struct Edge{int v,nxt; }edge[N]; int n,cnt,head[N]; int fa[N],sz[N],son[N],ind,dfn[N],rnk[N],top[N],bot[N]; int rev[M],inv[M],w[20][M],iw[20][M],A[M],B[M]; vector<int> poly[N],f[N<<2],g[N<<2]; int add(int a,int b){a=a+b;if(a>mod) return a-mod;return a; } int dec(int a,int b){a=a-b;if(a<0) return a+mod;return a; } int mul(int a,int b){return 1ll*a*b%mod; } int power(int a,int b){int res=1;while(b){ if(b&1){res=mul(res,a);}b>>=1;a=mul(a,a);}return res; } void init(int len){inv[1]=1;for(int i=2;i<=len;i++) inv[i]=mul(inv[mod%i],dec(mod,mod/i));for(int i=1,t=0;i<len;i<<=1,t++){int wn=power(3,(mod-1)/i/2),iwn=power(wn,mod-2);for(int j=0;j<len;j+=(i<<1)){int w=1,iw=1;for(int k=j;k<j+i;k++,w=mul(w,wn),iw=mul(iw,iwn)){::w[t][k]=w;::iw[t][k]=iw;}}} } void NTT(int a[],int len,int op){//op=0:系數(shù)轉點值,op=1:點值轉系數(shù) for(int i=0;i<len;i++){rev[i]=(rev[i>>1]>>1)|((i&1)*(len>>1));if(i<rev[i])swap(a[i],a[rev[i]]);}for(int i=1,t=0;i<len;i<<=1,t++){for(int j=0;j<len;j+=(i<<1)){int x,y;for(int k=j;k<j+i;k++){x=a[k];if(!op) y=mul(w[t][k],a[k+i]);else if(op) y=mul(iw[t][k],a[k+i]);a[k]=add(x,y);a[k+i]=dec(x,y);}}}if(op){for(int i=0;i<len;i++)a[i]=mul(a[i],inv[len]);} } vector<int> operator + (const vector<int> &a,const vector<int> &b){int n=a.size(),m=b.size();vector<int> c(max(n,m));for(int i=0;i<n;i++) c[i]=a[i];for(int i=0;i<m;i++) c[i]=add(c[i],b[i]);return c; } vector<int> operator * (const vector<int> &a,const vector<int> &b){int n=a.size(),m=b.size();vector<int> c(n+m-1);int len;for(len=1;len<=n+m;len<<=1);for(int i=0;i<len;i++){A[i]=i<n?a[i]:0;B[i]=i<m?b[i]:0;}NTT(A,len,0);NTT(B,len,0);for(int i=0;i<len;i++)A[i]=mul(A[i],B[i]);NTT(A,len,1);for(int i=0;i<n+m-1;i++) c[i]=A[i];return c; } void addedge(int u,int v){edge[++cnt].v=v;edge[cnt].nxt=head[u];head[u]=cnt; } void dfs1(int u){sz[u]++;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;dfs1(v);sz[u]+=sz[v];if(sz[v]>sz[son[u]]) son[u]=v;} } void dfs2(int u,int tp){dfn[u]=++ind;rnk[ind]=u;top[u]=tp;bot[tp]=u;if(!son[u]) return;dfs2(son[u],tp);for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(v!=son[u]) dfs2(v,v);} } void solve(vector<int> &sons,int u,int l,int r){if(l==r){f[u]=poly[sons[l]];return;}int mid=(l+r)>>1;solve(sons,u<<1,l,mid);solve(sons,u<<1|1,mid+1,r);f[u]=f[u<<1]*f[u<<1|1];f[u<<1].clear();f[u<<1|1].clear(); } void merge(int u,int l,int r){if(l==r){f[u]=g[u]=poly[rnk[l]];return;}int mid=(l+r)>>1;merge(u<<1,l,mid);merge(u<<1|1,mid+1,r);f[u]=f[u<<1]*f[u<<1|1];g[u]=g[u<<1]+f[u<<1]*g[u<<1|1];//g=f1+f1f2+f1f2f3+...f[u<<1].clear();f[u<<1|1].clear();g[u<<1].clear();g[u<<1|1].clear(); } void dp(int u){if(!son[u]){poly[u].push_back(0);//0*x^0poly[u].push_back(1);//1*x^1return;}dp(son[u]);vector<int> lis;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(v!=son[u]){dp(v);lis.push_back(v);}}if(lis.size()){solve(lis,1,0,lis.size()-1);//分治NTT合并輕兒子信息 poly[u]=f[1];}else{ poly[u].push_back(1);//1*x^0}if(u==top[u]){merge(1,dfn[u],dfn[bot[u]]-1);//分治NTT合并重鏈信息 //注意-1poly[u].clear();poly[u].push_back(0);//0*x^0for(int i=0,sz=g[1].size();i<sz;i++){poly[u].push_back(g[1][i]);}poly[u][1]=add(poly[u][1],1);//x^1項的次數(shù)+1 } } int main(){scanf("%d",&n);for(int i=2;i<=n;i++){scanf("%d",&fa[i]);addedge(fa[i],i);}dfs1(1);dfs2(1,1);int len=1;while(len<=n) len<<=1;init(len);dp(1);while((int)poly[1].size()<=n) poly[1].push_back(0);int ans=0,fac=1,x;for(int i=1;i<=n;i++){scanf("%lld",&x);fac=mul(fac,i);ans=add(ans,mul(x,mul(poly[1][i],fac)));}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的[XSY] 树与图（树形DP、生成函数、分治NTT、重链剖分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。