找别人网站开发没给我源代码,微信网站建设费记什么科目,鸿蒙最新版本,如何用电脑主机做网站树与图 如果真的在图上跑算法#xff0c;那么光建图复杂度就O(n2logn)O(n^2logn)O(n2logn)了#xff0c;这显然不可行。所以一定要把 在图上的操作 转换成 在树上的操作 在图上删去点u#xff0c;相当于在树上删去u到根节点的链#xff0c;并把u的整棵子树删掉 如果我们枚举…树与图 如果真的在图上跑算法那么光建图复杂度就O(n2logn)O(n^2logn)O(n2logn)了这显然不可行。所以一定要把 在图上的操作 转换成 在树上的操作 在图上删去点u相当于在树上删去u到根节点的链并把u的整棵子树删掉 如果我们枚举算法可能产生的所有过程然后再去求每个过程对应的删点次数那么光枚举过程就已经可以T爆了 所以我们只能枚举删点次数然后求出该删掉次数对应多少种过程 这可以用树形DP实现时间复杂度O(n3)O(n^3)O(n3) 可以想到用生成函数进一步优化即用次数来代表删点次数系数来代表可能过程种数这样合并两棵子树时直接用NTT把两棵子树的多项式乘起来即可 这样会产生两个问题 代码中每一步合并乘的CjkkC_{jk}^{k}Cjkk怎么办 NTT的时间复杂度是O(nlogn)O(nlogn)O(nlogn)(这里n指多项式的最高次数)\color{Red}(这里n指多项式的最高次数)(这里n指多项式的最高次数)这样总时间复杂度就是O(n3logn)O(n^3logn)O(n3logn)怎么还变大了 就是这两个问题让我在考场上没有继续写下去 对于第一个问题我后来想到其实不一定要在DP过程中乘CjkkC_{jk}^{k}CjkkDP完后再统一乘删点次数删点次数删点次数来定序也是可行的 对于第二个问题在更新u时直接用 分治NTT 把u的所有儿子上的多项式 一起 乘起来不要那么傻逼想着用NTT一个接一个乘 这样时间复杂度降为O(n2log2n)O(n^2log^2n)O(n2log2n)但还是会T 题目的时间复杂度很大程度上取决于NTT时多项式的最高次数而多项式次数与删点次数有关所以考虑一下我们最多能删几个点 发现所选的要删的点满足如下规律所选的任意两个点都不互为祖先关系且从根到每个叶子的路径上都恰好有一个被选择的点 即u点的多项式的最高次数u子树内叶节点的个数\color{Red}u点的多项式的最高次数u子树内叶节点的个数u点的多项式的最高次数u子树内叶节点的个数进一步地因为每个节点的多项式最高次数至少为1所以u点的多项式最多是(u子树内叶节点个数)个多项式相乘的结果\color{Red}u点的多项式最多是(u子树内叶节点个数)个多项式相乘的结果u点的多项式最多是(u子树内叶节点个数)个多项式相乘的结果 设leafuleaf_uleafu表示u的子树中叶子的个数则在u点分治NTT的时间总和leafu(log2leafu)leaf_u(log^2leaf_u)leafu(log2leafu)整道题的总时间∑u1nleafu(log2leafu)\sum_{u1}^{n}leaf_u(log^2leaf_u)∑u1nleafu(log2leafu) 考虑两种极端情况一种是菊花图一种是一条很长的树链上面随机的挂上一些类似菊花图深度小但点度数大的子树 按照上面的做法菊花图的时间复杂度可以做到O(nlog2n)O(nlog^2n)O(nlog2n)树链的时间复杂度却逼近O(n2log2n)O(n^2log^2n)O(n2log2n) 我们考虑给树链换一种做法 枚举在链上删了哪个点这样一来整条链和被删点的子树都会被删除而被删点上方的子树不会被删除并且相互独立了。 因此如果链上的点的多项式为F1(x),F2(x),F3(x)...F_1(x),F_2(x),F_3(x)...F1(x),F2(x),F3(x)...(按点深度由浅到深编号)那么最后求出这条链的多项式为F1(x)F1(x)F2(x)F1(x)F2(x)F3(x)...F_1(x)F_1(x)F_2(x)F_1(x)F_2(x)F_3(x)...F1(x)F1(x)F2(x)F1(x)F2(x)F3(x)... 用分治NTT做总时间leaf1(log2leaf1)leaf_1(log^2leaf_1)leaf1(log2leaf1)所以时间复杂度为O(nlog2n)O(nlog^2n)O(nlog2n) 考虑把这两种做法结合起来即对树进行重链剖分然后对每个节点的轻儿子分治NTT对每条重链分治 NTT 具体来说设fu(x)f_u(x)fu(x)表示u点的多项式 深搜遍历每个节点假设当前遍历到u 若u为叶子节点fu(x)xf_u(x)xfu(x)x返回 若不是执行下述步骤 ①若节点u有轻儿子fu(x)∏v∈lightsonfv(x)f_u(x)\prod_{v\in lightson}f_v(x)fu(x)∏v∈lightsonfv(x) 若没有fu(x)1f_u(x)1fu(x)1 ②若节点为重链端点 设这条重链上的点由浅至深分别为p1,p2,⋯,pkp_1,p_2,⋯,p_kp1,p2,⋯,pk。显然p1p_1p1为链头pkp_kpk为叶子节点。 fp1(x)fp1(x)fp1(x)fp2(x)fp1(x)fp2(x)fp3(x)...fp1(x)fp2(x)fp3(x)...fpk−1xf_{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}}xfp1(x)fp1(x)fp1(x)fp2(x)fp1(x)fp2(x)fp3(x)...fp1(x)fp2(x)fp3(x)...fpk−1x xxx是因为要考虑删去自己的情况 分析一下这样做的时间复杂度整道题的总时间∑u∈topleafu(log2leafu)∑u1n(∑v∈lightsonuleafv)[log2(∑v∈lightsonuleafv)]\sum_{u\in top}leaf_u(log^2leaf_u)\sum_{u1}^{n}(\sum_{v\in lightson_u}leaf_v)[log^2(\sum_{v\in lightson_u}leaf_v)]∑u∈topleafu(log2leafu)∑u1n(∑v∈lightsonuleafv)[log2(∑v∈lightsonuleafv)] ∑u∈topleafu(log2leafu)∑u∈topleafu(log2n)log2n∑u∈topleafu\sum_{u\in top}leaf_u(log^2leaf_u)\sum_{u\in top}leaf_u(log^2n)log^2n\sum_{u\in top}leaf_u∑u∈topleafu(log2leafu)∑u∈topleafu(log2n)log2n∑u∈topleafu 。因为每个叶子节点到根节点的路径上最多有lognlognlogn条重链而每个叶子节点又只在其到根节点的路径上的重链头处对∑u∈topleafu\sum_{u\in top}leaf_u∑u∈topleafu有1的贡献所以∑u∈topleafunlogn\sum_{u\in top}leaf_unlogn∑u∈topleafunlogn∑u∈topleafu(log2leafu)nlog3n\sum_{u\in top}leaf_u(log^2leaf_u)nlog^3n∑u∈topleafu(log2leafu)nlog3n ∑u1n(∑v∈lightsonuleafv)[log2(∑v∈lightsonuleafv)]∑u1n(∑v∈lightsonuleafv)(log2n)log2n∑u1n(∑v∈lightsonuleafv)\sum_{u1}^{n}(\sum_{v\in lightson_u}leaf_v)[log^2(\sum_{v\in lightson_u}leaf_v)]\sum_{u1}^{n}(\sum_{v\in lightson_u}leaf_v)(log^2n)log^2n\sum_{u1}^{n}(\sum_{v\in lightson_u}leaf_v)∑u1n(∑v∈lightsonuleafv)[log2(∑v∈lightsonuleafv)]∑u1n(∑v∈lightsonuleafv)(log2n)log2n∑u1n(∑v∈lightsonuleafv) 。因为每个叶子节点到根节点的路径上最多有lognlognlogn条轻边即每个叶子节点最多只在lognlognlogn个祖先处对∑u1n(∑v∈lightsonuleafv)\sum_{u1}^{n}(\sum_{v\in lightson_u}leaf_v)∑u1n(∑v∈lightsonuleafv)有1的贡献所以∑u1n(∑v∈lightsonuleafv)nlogn\sum_{u1}^{n}(\sum_{v\in lightson_u}leaf_v)nlogn∑u1n(∑v∈lightsonuleafv)nlogn∑u1n(∑v∈lightsonuleafv)[log2(∑v∈lightsonuleafv)]nlog3n\sum_{u1}^{n}(\sum_{v\in lightson_u}leaf_v)[log^2(\sum_{v\in lightson_u}leaf_v)]nlog^3n∑u1n(∑v∈lightsonuleafv)[log2(∑v∈lightsonuleafv)]nlog3n 因此总时间复杂度是O(nlog3n)O(nlog^3n)O(nlog3n)但由于树剖logloglog小和跑不满等原因可以跑过
最后树剖分轻重儿子维护的处理类似这题可以一起记忆
#includeiostream
#includecstdio
#includevector
using namespace std;
typedef long long ll;
const int mod998244353;
const int N100010;
const int M250000;
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];
vectorint poly[N],f[N2],g[N2];
int add(int a,int b){aab;if(amod) return a-mod;return a;
}
int dec(int a,int b){aa-b;if(a0) return amod;return a;
}
int mul(int a,int b){return 1ll*a*b%mod;
}
int power(int a,int b){int res1;while(b){ if(b1){resmul(res,a);}b1;amul(a,a);}return res;
}
void init(int len){inv[1]1;for(int i2;ilen;i) inv[i]mul(inv[mod%i],dec(mod,mod/i));for(int i1,t0;ilen;i1,t){int wnpower(3,(mod-1)/i/2),iwnpower(wn,mod-2);for(int j0;jlen;j(i1)){int w1,iw1;for(int kj;kji;k,wmul(w,wn),iwmul(iw,iwn)){::w[t][k]w;::iw[t][k]iw;}}}
}
void NTT(int a[],int len,int op){//op0:系数转点值,op1:点值转系数 for(int i0;ilen;i){rev[i](rev[i1]1)|((i1)*(len1));if(irev[i])swap(a[i],a[rev[i]]);}for(int i1,t0;ilen;i1,t){for(int j0;jlen;j(i1)){int x,y;for(int kj;kji;k){xa[k];if(!op) ymul(w[t][k],a[ki]);else if(op) ymul(iw[t][k],a[ki]);a[k]add(x,y);a[ki]dec(x,y);}}}if(op){for(int i0;ilen;i)a[i]mul(a[i],inv[len]);}
}
vectorint operator (const vectorint a,const vectorint b){int na.size(),mb.size();vectorint c(max(n,m));for(int i0;in;i) c[i]a[i];for(int i0;im;i) c[i]add(c[i],b[i]);return c;
}
vectorint operator * (const vectorint a,const vectorint b){int na.size(),mb.size();vectorint c(nm-1);int len;for(len1;lennm;len1);for(int i0;ilen;i){A[i]in?a[i]:0;B[i]im?b[i]:0;}NTT(A,len,0);NTT(B,len,0);for(int i0;ilen;i)A[i]mul(A[i],B[i]);NTT(A,len,1);for(int i0;inm-1;i) c[i]A[i];return c;
}
void addedge(int u,int v){edge[cnt].vv;edge[cnt].nxthead[u];head[u]cnt;
}
void dfs1(int u){sz[u];for(int ihead[u];i;iedge[i].nxt){int vedge[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 ihead[u];i;iedge[i].nxt){int vedge[i].v;if(v!son[u]) dfs2(v,v);}
}
void solve(vectorint sons,int u,int l,int r){if(lr){f[u]poly[sons[l]];return;}int mid(lr)1;solve(sons,u1,l,mid);solve(sons,u1|1,mid1,r);f[u]f[u1]*f[u1|1];f[u1].clear();f[u1|1].clear();
}
void merge(int u,int l,int r){if(lr){f[u]g[u]poly[rnk[l]];return;}int mid(lr)1;merge(u1,l,mid);merge(u1|1,mid1,r);f[u]f[u1]*f[u1|1];g[u]g[u1]f[u1]*g[u1|1];//gf1f1f2f1f2f3...f[u1].clear();f[u1|1].clear();g[u1].clear();g[u1|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]);vectorint lis;for(int ihead[u];i;iedge[i].nxt){int vedge[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(utop[u]){merge(1,dfn[u],dfn[bot[u]]-1);//分治NTT合并重链信息 //注意-1poly[u].clear();poly[u].push_back(0);//0*x^0for(int i0,szg[1].size();isz;i){poly[u].push_back(g[1][i]);}poly[u][1]add(poly[u][1],1);//x^1项的次数1 }
}
int main(){scanf(%d,n);for(int i2;in;i){scanf(%d,fa[i]);addedge(fa[i],i);}dfs1(1);dfs2(1,1);int len1;while(lenn) len1;init(len);dp(1);while((int)poly[1].size()n) poly[1].push_back(0);int ans0,fac1,x;for(int i1;in;i){scanf(%lld,x);facmul(fac,i);ansadd(ans,mul(x,mul(poly[1][i],fac)));}printf(%lld\n,ans);return 0;
}
