小说网站开发教程,江西最新消息,制作网站难不难,wordpress询价功能正题
题目链接:https://www.luogu.org/problemnew/show/P1600 题目大意
一棵nnn个点的树#xff0c;通过每条边需要时间为1。有mmm个玩家从SiS_iSi跑到TiT_iTi#xff08;不停留#xff0c;跑完之后马上消失#xff09;。然后对于第iii个点求第wiw_iwi刻停留在改点…正题
题目链接:https://www.luogu.org/problemnew/show/P1600 题目大意
一棵nnn个点的树通过每条边需要时间为1。有mmm个玩家从SiS_iSi跑到TiT_iTi不停留跑完之后马上消失。然后对于第iii个点求第wiw_iwi刻停留在改点的玩家数量。 解题思路
对于每条路径我们拆分成两段算是树上差分的一个变形
自S−gt;lcaS-gt;lcaS−lca然后当该路径上一个点满足depiwidepSdep_iw_idep_SdepiwidepS则经过改点。 对于这种情况我们用cnticnt_icnti表示起点为iii的人个数VsiVs_iVsi表示lcalcalca在iii点的路径的起点深度集合。然后用vupivup_ivupi表示目前depSidep_SidepSi的路径个数自lca−gt;Elca-gt;Elca−E然后当改点上一个点满足depi−wi2∗deplca−depsdep_i-w_i2*dep_{lca}-dep_sdepi−wi2∗deplca−deps则经过改点。 为了方便陈述我们定义num2∗deplca−depsnum2*dep_{lca}-dep_snum2∗deplca−deps 对于这种情况我们用cnt2icnt2_icnt2i表示终点为iii的路径numnumnum集合VtiVt_iVti表示lcalcalca在iii点的路径的numnumnum集合。然后用vdownivdown_ivdowni表示目前numinuminumi的路径个数
然后就完成了不过要注意depi−widep_i-w_idepi−wi可能为负数所以我们需要加上一个大整数NNN。(PascalPascalPascal就莫得问题了) codecodecode
#includecstdio
#includealgorithm
#includequeue
#includecmath
#includevector
using namespace std;
const int N310000;
struct line{int to,next;
}a[N*5];
int tot,n,m,ls[N],dep[N],f[N][30];
int vup[4*N],vdown[4*N],cnt[N],T,ans[N],w[N];
vectorint Vs[N],Vt[N],cnt2[N];
queueint q;
inline int read()
{int X0,w0; char c0;while(c0||c9) {w|c-;cgetchar();}while(c0c9) X(X3)(X1)(c^48),cgetchar();return w?-X:X;
}
inline void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
inline void bfs(int s)
{q.push(s);dep[s]1;while(!q.empty()){int xq.front();q.pop();for (int ils[x];i;ia[i].next){int ya[i].to;if (dep[y]) continue;q.push(y);f[y][0]x;dep[y]dep[x]1;}}T(int)(log(n)/log(2))1;for (int j1;jT;j)for (int i1;in;i)f[i][j]f[f[i][j-1]][j-1];
}
inline int LCA(int x,int y)
{if (dep[x]dep[y]) swap(x,y);for (int iT;i0;i--)if (dep[f[y][i]]dep[x]) yf[y][i];if (xy) return x;for (int iT;i0;i--)if (f[y][i]!f[x][i]) {xf[x][i];yf[y][i];}return f[x][0];
}
void dfs(int x,int fa)
{int nupdep[x]w[x]N,ndowndep[x]-w[x]N;int lastvup[nup]vdown[ndown];vup[dep[x]N]cnt[x];for(int i0;icnt2[x].size();i)vdown[cnt2[x][i]N];for(int i0;iVs[x].size();i)vup[Vs[x][i]N]--;for(int i0;iVt[x].size();i)vdown[Vt[x][i]N]--;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa) continue;dfs(y,x);}ans[x]vup[dep[x]w[x]N]vdown[dep[x]-w[x]N]-last;
}
int main()
{nread();mread();for(int i1;in;i){int x,y;xread();yread();addl(x,y);addl(y,x);}for(int i1;in;i)w[i]read();bfs(1);for(int i1;im;i){int s,t;sread();tread();int lcaLCA(s,t);cnt[s];Vs[f[lca][0]].push_back(dep[s]);cnt2[t].push_back(2*dep[lca]-dep[s]);Vt[lca].push_back(2*dep[lca]-dep[s]);}dfs(1,1);for(int i1;in;i)printf(%d ,ans[i]);
}
