个人如何免费建网站,大连seo建站,青岛关键词搜索排名,安阳360网站推广工具Description
一棵 n 个点的有根树#xff0c;带点权 wi。 从 s 出发#xff0c;希望达到 t#xff0c;每秒可以从当前点移动到某一个儿子。 有一个死亡次数#xff0c;初始为 0。若在某个点 i(i ! s, t) 时#xff0c;死亡次数 ≤ wi#xff0c;那么死亡次数自增 1…Description
一棵 n 个点的有根树带点权 wi。 从 s 出发希望达到 t每秒可以从当前点移动到某一个儿子。 有一个死亡次数初始为 0。若在某个点 i(i ! s, t) 时死亡次数 ≤ wi那么死亡次数自增 1并且立刻跳回到 s。 给出 q 组 s, t求最短时间。 n, q ≤ 3×1053 \times 10^53×105
Solution
每次从点 s 出生到撞程序猿死亡跟前几次是怎么死的并没有关系。所以对于每次 “从点 s 出生到撞程序猿死亡” 的过程都可以贪心选最近的点早死早超生。产生一个朴素的想法记 gi,jg_i,_jgi,j 为当前在 i已死亡 j − 1 次再死一次所需时间。若 s, t 路径上最大点权为 W那么答案为 ∑i1Wgs,idis(s,t)\sum _{i1}^W g_s,_i dis(s, t)∑i1Wgs,idis(s,t)。这样设计状态的复杂度太大发现 g 单调并且有大量状态相同。图像的话大概长这样 优化换个角度考虑有多少次从出生到死亡的过程需要一秒多少次需要两秒等等。具体来说考虑记录 f[i][j] 表示 i 的子树中和 i 距离小于等于 j 的点的权值最大值。 这样 f[i][j]−f[i][j−1] 就等于有多少次从出生到死亡需要 j 秒。那么对于一个询问(s,t)答案就是 ∑i1ddep[pos[mxval]]−dep[s](f[s][i]−f[s][i−1])∗idis(s,t)\sum_{i1}^{ddep[pos[mxval]]-dep[s]}(f[s][i]-f[s][i-1])*idis(s,t)∑i1ddep[pos[mxval]]−dep[s](f[s][i]−f[s][i−1])∗idis(s,t) f[s][d]∗d−∑i1d−1f[s][i]dis(s,t)f[s][d]*d-\sum_{i1}^{d-1}f[s][i]dis(s,t)f[s][d]∗d−∑i1d−1f[s][i]dis(s,t)。所以可以把询问按照 s 挂在树上想办法维护f离线求解。考虑如何维护f。因为它与深度有关所以考虑长链剖分。长链剖分完后有两种合并链的方法
法一用一个点v去更新f是区间对一个数取max的操作但因为f单调递增所以可以二分出第一个大于 v 的位置然后区间覆盖就可以了。这个可以用线段树实现。(推荐按照树剖的DFS序建一棵线段树然后所有操作都可以在这一棵线段树上做。) 时间复杂度 O((nq)logn)O((nq)logn)O((nq)logn)。法二若dep[j]dep[k]且w[j]w[k]那么k点显然可以不用维护了发现删掉类似k的点后我们就得到了一个单调栈因此我们决定维护一个子树内部按照深度排好序后对于 w 的单调栈。询问直接二分就好。注意点1.我们需要求单调栈从栈顶到栈底的前缀和但是不好维护所以选择维护后缀和。2.栈的合并实际上按照任意顺序时间复杂度都是O(n)O(n)O(n)但是我们需要注意空间为省空间我们长链剖分之后按照DFS序分配空间即可。 时间复杂度 O(nqlogn)O(nqlogn)O(nqlogn)。
Code
#includeiostream
#includecstdio
#includevector
using namespace std;
const int N3e55;
struct Edge{int v,nxt;}edge[N];
int n,m,w[N],cnt,head[N];
int fa[N][25],mxw[N][25],len[N],son[N],dep[N],dfn[N],ind;
struct Query{int y,id;};
vectorQuery d[N];
long long ans[N];
int L[N],R[N],tot;
long long sum[N];//sum维护后缀和
struct Stack{int dep,w;}stk[N],q[N];
//用stk来记录单调栈是为了省空间
//按dfs序分配空间即可保证每个点对应的栈使用的stk区间无重叠部分
void addedge(int u,int v){edge[cnt].vv;edge[cnt].nxthead[u];head[u]cnt;
}
void dfs1(int u){dep[u]dep[fa[u][0]]1;mxw[u][0]w[fa[u][0]];for(int i1;i20;i){fa[u][i]fa[fa[u][i-1]][i-1];mxw[u][i]max(mxw[u][i-1],mxw[fa[u][i-1]][i-1]);}for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;dfs1(v);if(len[v]len[son[u]]) son[u]v;}len[u]len[son[u]]1;
}
int get_mxw(int x,int y){int ret0;for(int i20;i0;i--)if(dep[fa[x][i]]dep[y])retmax(ret,mxw[x][i]),xfa[x][i];return ret;
}
void add(int x,Stack a){//从x点的栈的左端加入新元素 //新加入元素的dep保证栈中元素的dep的最小值 while(L[x]R[x]stk[L[x]].wa.w) L[x];if(L[x]R[x]){sum[--L[x]]0;stk[L[x]]a;} else{if(stk[L[x]].depa.dep){stk[--L[x]]a;sum[L[x]]sum[L[x]1]1ll*stk[L[x]1].dep*(stk[L[x]1].w-a.w);}}
}
void merge(int x,int y){//往x点的栈加入y点的栈中的元素时仍要满足x点的栈中的元素dep值从小到大排布 tot0;while(L[x]R[x]stk[L[x]].depstk[R[y]].dep) q[tot]stk[L[x]];while(totL[y]R[y])if(q[tot].depstk[R[y]].dep) add(x,q[tot--]);else add(x,stk[R[y]--]);while(tot) add(x,q[tot--]);while(L[y]R[y]) add(x,stk[R[y]--]);
}
long long query(int u,int v){int mxget_mxw(v,u),lL[u],rR[u],mid;while(lr){midlr1;if(stk[mid].wmx) lmid1;else rmid-1;}if(stk[L[u]].wmx)return 1ll*sum[L[u]]- 1ll*sum[l] 1ll*stk[L[u]].dep*stk[L[u]].w - 1ll*dep[u]*mx - 1ll*(stk[l].w-mx)*stk[l].dep;elsereturn 1ll*mx*(stk[l].dep-dep[u]);
}
void dfs2(int u){dfn[u]ind;if(son[u]){dfs2(son[u]);L[u]L[son[u]];R[u]R[son[u]];}else{L[u]ind;R[u]ind-1;}for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;if(vson[u]) continue;dfs2(v);merge(u,v);}for(int i0;id[u].size();i){int vd[u][i].y;int idd[u][i].id;ans[id]query(u,v)dep[v]-dep[u];}add(u,(Stack){dep[u],w[u]});
}
int main(){scanf(%d,n);for(int i1;in;i) scanf(%d,w[i]);for(int i2;in;i){scanf(%d,fa[i][0]);addedge(fa[i][0],i);}dfs1(1);scanf(%d,m);for(int i1;im;i){int u,v;scanf(%d%d,u,v);d[u].push_back((Query){v,i}); }dfs2(1);for(int i1;im;i)printf(%lld\n,ans[i]);return 0;
}参考文章 https://vfleaking.blog.uoj.ac/blog/2292 https://www.cnblogs.com/penth/p/9801945.html https://blog.csdn.net/qq_42555009/article/details/100934540 https://blog.csdn.net/zxyoi_dreamer/article/details/101705010 https://blog.csdn.net/Mr_wuyongcong/article/details/111996460
