建营销型网站,wordpress阅读最多插件,旅游seo,百度统计官网绿色
题意简述 题解
首先#xff0c;每次修改完点权后#xff0c;重新考虑一遍所有路径显然是不现实的#xff0c;所以我们考虑求出经过每个点的两端同色的简单路径数#xff0c;这样权值和容易统计和修改。 接下来分析仙人掌上的简单路径性质。一条简单路径上的边…绿色
题意简述 题解
首先每次修改完点权后重新考虑一遍所有路径显然是不现实的所以我们考虑求出经过每个点的两端同色的简单路径数这样权值和容易统计和修改。 接下来分析仙人掌上的简单路径性质。一条简单路径上的边可以分为桥边和环上的边。过桥只有一种方法而过同一个环有两个方向的环边可选。
现在我们选取一个关键点强制简单路径必须通过该点。如果关键点在一个环上且该简单路径在该环上的第一个和最后一个点均不是关键点那么该环只有一个方向的环边可选。
建立原仙人掌的圆方树。 如果定义方点贡献 2 种方案圆点贡献 1 种方案一条路径贡献方案数为所有点贡献方案数之积那么原仙人掌上两个同色点间的路径数转化为对应圆点间的简单路径方案数。
在所有的树上简单路径中 如果它通过关键点则贡献值为该路径的方案数 如果它不通过关键点但是通过关键点的某相邻方点则贡献该路径方案数的一半。 考虑用何算法求出经过每个点的两端同色的简单路径数(记过uuu的简单路径数为coe[u]coe[u]coe[u])
法一暴力枚举
按题意枚举所有同色点对可解决n≤100n≤100n≤100的子任务。
法二树形DP
首先枚举每一种颜色每次只考虑当前颜色的同色点对的贡献。 对于树上任意一点uuu我们可以求出 dp[u]dp[u]dp[u] uuu的子树内当前色的圆点到uuu的路径数 up[u]up[u]up[u] uuu的子树外当前色的圆点到uuu的路径数 换根DP 那么过uuu的简单路径数coe[u](dp[u]up[u]1)2−dp[u]2−dp[v]2−122coe[u]\frac{(dp[u]up[u]1)^2-dp[u]^2-dp[v]^2-1^2}{2}coe[u]2(dp[u]up[u]1)2−dp[u]2−dp[v]2−12
这样可以解决n≤105,k≤5n\leq10^5,k\leq5n≤105,k≤5的子任务
优化建虚树
处理树上询问点两两间路径的并的问题一个常见的套路是构建询问点的虚树因为虚树中同一条边上的点受询问点的影响一致把这些点一起处理可大大提高效率
于是我们构建同色点的虚树通过前缀和预处理虚树每条边上压缩的点贡献的方案数作为边的方案数。
对于过虚树节点的简单路径数可以在树形dp时直接统计出来 对于过虚树边上压缩掉的点的简单路径数可以利用树上差分与前缀和快速处理。
那么接下来仅需考虑 过关键点相邻的方点的路径总方案数 即可 计算通过了每个相邻方点的路径总方案数再减去通过了它们之间相邻边的方案数。
不难发现上述树上差分与前缀和的方法已经预处理了通过各边的路径方案数。
此算法时间复杂度O(nlogn)O(n log n)O(nlogn)、空间复杂度O(n)O(n)O(n)
#includebits/stdc.h
using namespace std;
const int mod1e97;
const int inv2(mod1)/2;
namespace modular{int add(int a,int b){return abmod?ab-mod:ab;}int dec(int a,int b){return a-b0?a-bmod:a-b;}int mul(int a,int b){return 1ll*a*b%mod;}void Add(int a,int b){aadd(a,b);}void Dec(int a,int b){adec(a,b);}void Mul(int a,int b){amul(a,b);}
}
using namespace modular;
inline int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}
const int N1e610;
int n,m,k,pw[N];
int c[N],w[N];
vectorint S[N];int cnt,head[N],to[N1],nxt[N1];
int coe[N],nd;
vectorint e[N];
int in[N],out[N],dfn,fr[N];
bool is[N];
void addedge(int u,int v){to[cnt]v;nxt[cnt]head[u];head[u]cnt;
}
void build(int u,int pre){//建圆方树 in[u]dfn;for(int ihead[u];i;inxt[i]){if(!((i^1)^pre)) continue;//条件一定不能改 int vto[i];if(!in[v]){fr[v]u;build(v,i);//记来边而不是来点 }else if(in[v]in[u]){nd;e[nd].push_back(v);e[v].push_back(nd);for(int xu;x!v;xfr[x]){is[x]1;e[nd].push_back(x);e[x].push_back(nd);}}}
}int ct[N],fa[N],sz[N],son[N],dep[N],top[N];
void sub_dfs(int u,int f){in[u]dfn;sz[u]1;fa[u]f;dep[u]dep[f]1;for(int i0;ie[u].size();i){int ve[u][i];if(vf) continue;ct[v]ct[u](un);sub_dfs(v,u);sz[u]sz[v];if(sz[v]sz[son[u]]) son[u]v;}out[u]dfn;
}
void tp_dfs(int u,int tp){top[u]tp;if(!son[u]) return;tp_dfs(son[u],tp);for(int i0;ie[u].size();i){int ve[u][i];if(v!fa[u]v!son[u]) tp_dfs(v,v);}
}
int LCA(int x,int y){while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]) swap(x,y);xfa[top[x]];}return dep[x]dep[y]?x:y;
}
bool sub(int x,int y){return in[x]in[y]in[y]out[x];
}int ta[N],dot[N];
//ta[u]记录过u,且过边(u,fa[u])的路径数(用树上差分求出,所以work时的ta是差分数组,u子树内的ta和才是实际路径数)
//dot[u]记录过u,但不过边(u,fa[u])的路径数
vectorint G[N];
int dp[N],up[N];
//dp[u]记录u子树内当前色的圆点到u的路径数
//up[u]记录u子树外当前色的圆点到虚树上u的父亲的路径数
bool o[N];
bool cmp(int x,int y){return in[x]in[y];
}
void dfs1(int u){dp[u]o[u];for(int i0;iG[u].size();i){int vG[u][i];dfs1(v);Add(dp[u],mul(pw[ct[v]-ct[u]],dp[v]));}
}
void dfs2(int u,int f){int c;if(f){cmul(up[u],dp[u]);Mul(c,pw[ct[u]-ct[f]-(fn)]);Add(ta[u],c);Dec(ta[f],c);Dec(dot[u],c);}cmul(pw[ct[u]-ct[f](un)-(fn)],up[u]);int Smul(c,c)o[u], alladd(dp[u],c);for(int i0;iG[u].size();i){int vG[u][i];cmul(pw[ct[v]-ct[u]],dp[v]);Add(S,mul(c,c));}Sdec(mul(all,all),S);Mul(S,inv2);if(un) Mul(S,inv2);Add(dot[u],S);for(int i0;iG[u].size();i){int vG[u][i];Add(up[v],dp[u]);Add(up[v],mul(pw[ct[u]-ct[f](un)-(fn)],up[u]));Dec(up[v],mul(pw[ct[v]-ct[u]],dp[v]));dfs2(v,u);}
}
void work(vectorint p){//对每种颜色的点建虚树,求解 sort(p.begin(),p.end(),cmp);static int ex[N],tim;tim;for(int i0;ip.size();i){int xp[i];ex[x]tim;o[x]1;}int np.size(),x,y,z;for(int i0;i1n;i){int xLCA(p[i],p[i1]);if(ex[x]!tim) ex[x]tim,p.push_back(x);}sort(p.begin(),p.end(),cmp);static int s[N];int top0;for(int i0;ip.size();i){xp[i];while(top1!sub(s[top],x)){ys[top],zs[top-1];G[z].push_back(y);top--;} s[top] x; }while(top1){ys[top],zs[top-1];G[z].push_back(y);top--;}dfs1(p[0]);dfs2(p[0],0);for(int i0;ip.size();i){int xp[i];up[x]o[x]0;G[x].clear();}p.clear();
}
void dfs(int u,int f){for(int i0;ie[u].size();i){int ve[u][i];if(vf) continue;dfs(v,u);Add(ta[u],ta[v]);}coe[u]mul(2,add(ta[u],dot[u]));for(int i0;ie[u].size();i){int ve[u][i];if(v!fvn) Add(coe[u],dot[v]);}
}
int main(){nread();mread();kread();pw[0]1;for(int i1;in;i) pw[i]add(pw[i-1],pw[i-1]);ndn;for(int i1;in;i){c[i]read();S[c[i]].push_back(i);}for(int i1;in;i) w[i]read();cnt1;for(int i1;im;i){int uread(),vread();addedge(u,v);addedge(v,u);}build(1,0);for(int i2;in;i){if(!is[i]){e[i].push_back(fr[i]);e[fr[i]].push_back(i);} }dfn0; sub_dfs(1,0);tp_dfs(1,1);for(int i1;ik;i) work(S[i]);dfs(1,0);for(int i2;in;i){int xfa[i];if(xn){int cadd(ta[x],dot[x]);Dec(c,ta[i]);Add(coe[i],c);}}for(int i1;in;i) Mul(coe[i],inv2);//trick:前面先计算系数的2倍,最后再/2 int ans0;for(int i1;in;i)Add(ans,mul(w[i],coe[i]));printf(%d\n,ans);int Qread();for(int i1;iQ;i){int xread(),vread();Add(ans,mul(v,coe[x]));printf(%d\n,ans);}return 0;
}
/*
4 5 2
1 2 1 2
1 2 3 4
1 2
1 2
2 3
2 4
3 4
1
3 1
*/
