英文企业网站建站,专业企业网站建设公司,国外购物网站哪个最好,在线做初中题网站如果没有时间的限制#xff0c;这题就是对每个点iii#xff0c;求经过iii的路径数#xff0c;用树上差分解决即可#xff1a;
枚举路径x→y{x\to y\{x→y{ a[x]1;a[y]1;a[x]1;a[y]1;a[x]1;a[y]1; a[lca(x,y)]−1;a[fa[lca(x,y)]]−2;a[lca(x,y)]-1;a[fa[lca(x,y)]]-2;a[lc…如果没有时间的限制这题就是对每个点iii求经过iii的路径数用树上差分解决即可
枚举路径x→y{x\to y\{x→y{ a[x]1;a[y]1;a[x]1;a[y]1;a[x]1;a[y]1; a[lca(x,y)]−1;a[fa[lca(x,y)]]−2;a[lca(x,y)]-1;a[fa[lca(x,y)]]-2;a[lca(x,y)]−1;a[fa[lca(x,y)]]−2; }\}}
枚举点i{i\{i{ 经过iii的路径数 以iii为根的子树中aaa的和 }\}}
用树状数组实现
考虑加上时间限制怎么做
我们把每条路径x→yx\to yx→y拆成上行段和下行段。 若点iii在x→yx\to yx→y的上行段上 iii点的观察员看到从xxx出发跑到yyy的玩家当且仅当 dep[x]−dep[i]w[i]dep[x]-dep[i]w[i]dep[x]−dep[i]w[i]即dep[i]w[i]dep[x]dep[i]w[i]dep[x]dep[i]w[i]dep[x] 若点iii在x→yx\to yx→y的下行段上 iii点的观察员看到从xxx出发跑到yyy的玩家当且仅当 dep[x]dep[y]−2dep[lca(x,y)]−(dep[y]−dep[i])w[i]dep[x]dep[y]-2dep[lca(x,y)]-(dep[y]-dep[i])w[i]dep[x]dep[y]−2dep[lca(x,y)]−(dep[y]−dep[i])w[i] 即dep[i]−w[i]2dep[lca(x,y)]−dep[x]dep[i]-w[i]2dep[lca(x,y)]-dep[x]dep[i]−w[i]2dep[lca(x,y)]−dep[x]
对于路径x→yx\to yx→y我们将其拆成 上行段p:x→lca(x,y)p:x\to lca(x,y)p:x→lca(x,y)在xxx方向上的儿子下行段q:lca(x,y)→yq:lca(x,y)\to yq:lca(x,y)→y并记v[p]dep[x]v[p]dep[x]v[p]dep[x]v[q]2dep[lca(x,y)]−dep[x]v[q]2dep[lca(x,y)]-dep[x]v[q]2dep[lca(x,y)]−dep[x]
对于点iii我们记vp[i]dep[i]w[i]v_p[i]dep[i]w[i]vp[i]dep[i]w[i]vq[i]dep[i]−w[i]v_q[i]dep[i]-w[i]vq[i]dep[i]−w[i]
那么iii点的观察员看到的玩家数 ∑\sum∑经过iii且满足v[p]vp[i]v[p]v_p[i]v[p]vp[i]的上行段ppp的数量 ∑\sum∑经过iii且满足v[q]vq[i]v[q]v_q[i]v[q]vq[i]的下行段qqq的数量
先把点按vp[i]v_p[i]vp[i]排序把上行段按v[p]v[p]v[p]排序按树上差分的套路计算上行段的贡献。
再把点按vq[i]v_q[i]vq[i]排序把下行段按v[q]v[q]v[q]排序按树上差分的套路计算下行段的贡献。
如此即可得到最终答案。
#includeiostream
#includecstdio
#includestack
#includealgorithm
using namespace std;
const int N1e610;
struct Edge{int v,nxt;
}edge[N1];
int n,m,w[N],cnt,head[N],ans[N];
int ind,dfn[N],siz[N],dep[N],fa[N][20];
struct Query{int nd,x;friend bool operator (Query a,Query b){return a.xb.x;}
}a[N1];
struct Data{int d,u,x;friend bool operator (Data a,Data b){return a.xb.x;}
}b[2][N];
int tot[2];
stackData s;
void addedge(int u,int v){edge[cnt].vv;edge[cnt].nxthead[u];head[u]cnt;
}
void dfs(int u){dfn[u]ind;siz[u]1;for(int i1;i19;i)fa[u][i]fa[fa[u][i-1]][i-1];for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;if(vfa[u][0]) continue;fa[v][0]u;dep[v]dep[u]1;dfs(v);siz[u]siz[v];}
}
int LCA(int u,int v){if(dep[u]dep[v]) swap(u,v);int diffdep[u]-dep[v];for(int i19;i0;i--){if(diff(1i)) ufa[u][i];}if(uv) return u;for(int i19;i0;i--){if(fa[u][i]!fa[v][i]){ufa[u][i];vfa[v][i];}}return fa[u][0];
}
int c[N];
int lowbit(int x){return x(-x);}
void add(int x,int v){if(!x) return;for(int ix;in;ilowbit(i)) c[i]v;
}
int sum(int x){int res0;for(int ix;i;i-lowbit(i)) resc[i];return res;
}
int main(){scanf(%d%d,n,m);for(int i1;in;i){int u,v;scanf(%d%d,u,v);addedge(u,v);addedge(v,u);}dep[1]1;dfs(1);for(int i1;in;i){scanf(%d,w[i]);a[i](Query){i,dep[i]w[i]};a[in](Query){i,dep[i]-w[i]};}sort(a1,an1);sort(an1,a2*n1);for(int i1;im;i){int s,t,lca;scanf(%d%d,s,t);lcaLCA(s,t);if(slca){b[1][tot[1]](Data){t,s,dep[s]};}else if(tlca){b[0][tot[0]](Data){s,t,dep[s]};}else{int sons;for(int i19;i0;i--){if(dep[fa[son][i]]dep[lca]) sonfa[son][i];}b[0][tot[0]](Data){s,son,dep[s]};b[1][tot[1]](Data){t,lca,2*dep[lca]-dep[s]};}}sort(b[0]1,b[0]tot[0]1);sort(b[1]1,b[1]tot[1]1);int p1;for(int i1;in;i){if(a[i].x!a[i-1].x){while(!s.empty()){Data tmps.top();s.pop();add(dfn[fa[tmp.u][0]],1);add(dfn[tmp.d],-1);}}for(;ptot[0]b[0][p].xa[i].x;p){if(a[i].x!a[i-1].xb[0][p].xa[i].x){Data tmpb[0][p];add(dfn[fa[tmp.u][0]],-1);add(dfn[tmp.d],1);s.push(tmp);}}ans[a[i].nd]sum(dfn[a[i].nd]siz[a[i].nd]-1)-sum(dfn[a[i].nd]-1);}while(!s.empty()){Data tmps.top();s.pop();add(dfn[fa[tmp.u][0]],1);add(dfn[tmp.d],-1);}p1;for(int in1;i2*n;i){if(a[i].x!a[i-1].x){while(!s.empty()){Data tmps.top();s.pop();add(dfn[fa[tmp.u][0]],1);add(dfn[tmp.d],-1);}}for(;ptot[1]b[1][p].xa[i].x;p){if(a[i].x!a[i-1].xb[1][p].xa[i].x){Data tmpb[1][p];add(dfn[fa[tmp.u][0]],-1);add(dfn[tmp.d],1);s.push(tmp);}}ans[a[i].nd]sum(dfn[a[i].nd]siz[a[i].nd]-1)-sum(dfn[a[i].nd]-1);}for(int i1;in;i)printf(%d ,ans[i]);return 0;
}
