- Link https://www.luogu.com.cn/problem/P1600
- Solution
真是惭愧, 现在才来做这道 noip 就应该做的题目. 可能不落实题目也是我 csp 惨败的原因吧.
把一个玩家的跑步路径拆成两段, 以后的统计也分开: 一段是从 \(s\)到 \(lca\)的上升路径, 一段是从 \(lca\)到 \(t\)的下降路径.
考虑上升路径. 对于路径上的某个点 \(i\), 要在 \(i\)处有贡献, 应该满足:\(dep_s-dep_i=w_i\),
移下项就有, 对点 \(i\)有贡献的上升路径应满足起点 \(s\)有:\(dep_s=dep_i+w_i\).
考虑下降路径. 对于路径上的某个点 \(i\), 要在 \(i\)处有贡献, 应该满足:\(dep_t-dep_i=len-w_i\), 其中 \(len\)是路径长度. 同样的, 移项以后可以得到一个左边是定值的式子:\(dep_t-len=dep_i-w_i\). 也就是某段下降路径要对 \(i\)有贡献是终点 \(t\)应满足的条件.
问题转化成: 求覆盖每个点的合法路径的条数. 而且合法的条件都是链的深度最大的点 (起点 / 终点) 满足某个式子.
这种整条链的计算类比一下序列上的区间修改, 是可以用差分解决的. 注意, 因为 lca 只被算一次, 所以拆边的时候放到任意一边就行了.
统计也有技巧. 因为每个点要求的合法条件不一样, 不太好一起统计, 而每个点拿出来单独求显然也不对. 但考虑到信息只跟子树有关, 所以可以全局开一个以 \(dep_s\)或者 \(dep_t-len\)为下标的桶, 每个点答案就是递归 \(i\)这棵子树前后, 桶中 \(dep_i+w_i\)或者 \(dep_i-w_i\)位置上的增量.
统计下降路径是桶下标有可能为负, 要平移一下.
- Code
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> PII;
- #define REP(i,a,b) for(int i=(a),ed=(b);i<=ed;++i)
- #define mp(a,b) make_pair((a),(b))
- #define pb(a) push_back((a))
- inline int read(){
- register int x=0,f=1;register char ch=getchar();
- while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
- while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
- return f?x:-x;
- }
- const int N=3e5+10;
- int n,m,w[N],bk[N<<1],ans[N];
- vector<int> E[N];
- vector<PII> opt[2][N];
- namespace TCP{
- int fa[N],tp[N],siz[N],son[N],dep[N];
- inline void dfs(int u,int pa){
- fa[u]=pa;siz[u]=1;dep[u]=dep[pa]+1;
- for(int v:E[u])
- if(v^pa){
- dfs(v,u);siz[u]+=siz[v];
- if(siz[v]>siz[son[u]])son[u]=v;
- }
- }
- inline void dfs(int u){
- if(!tp[u])tp[u]=u;
- if(son[u]){tp[son[u]]=tp[u];dfs(son[u]);}
- for(int v:E[u])
- if(v^fa[u]&&v^son[u])dfs(v);
- }
- inline int lca(int x,int y){
- while(tp[x]^tp[y])
- if(dep[tp[x]]>=dep[tp[y]])x=fa[tp[x]];
- else y=fa[tp[y]];
- return dep[x]>=dep[y]?y:x;
- }
- }using namespace TCP;
- inline void work(int u,int flg){
- int d=flg*N,bef=flg?bk[dep[u]-w[u]+d]:bk[dep[u]+w[u]+d];
- for(int v:E[u])if(v^fa[u])work(v,flg);
- for(PII nw:opt[flg][u])bk[nw.first+d]+=nw.second;
- ans[u]+=(flg?bk[dep[u]-w[u]+d]:bk[dep[u]+w[u]+d])-bef;
- }
- int main(){
- n=read(),m=read();
- REP(i,1,n-1){int u=read(),v=read();E[u].pb(v),E[v].pb(u);}
- REP(i,1,n)w[i]=read();
- dfs(1,0);dfs(1);
- REP(i,1,m){
- int s=read(),t=read(),p=lca(s,t),l=dep[s]+dep[t]-2*dep[p];
- opt[0][s].pb(mp(dep[s],1));opt[0][fa[p]].pb(mp(dep[s],-1));
- opt[1][t].pb(mp(dep[t]-l,1));opt[1][p].pb(mp(dep[t]-l,-1));
- }
- work(1,0);memset(bk,0,sizeof(bk));work(1,1);
- REP(i,1,n)printf("%d",ans[i]);
- puts("");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3365717.html