1 条题解
-
-1yejun LV 10 MOD @ 2019-06-06 15:57:46
将每个玩家的路径拆分出来考虑。具体地说,对于玩家i,从\(S_{i}\)到\(T_{i}\)的路径拆分为\(S_{i}\)到\(lca(S_{i},T_{i})\)和\(lca(S_{i},T_{i})\)到\(T_{i}\)。
首先考虑从\(S_{i}\)到\(lca(S_{i},T_{i})\)的路径。
若这条路径上的点x能够观察到玩家i。那么等价于\(d\left [ S_{i} \right ]-d\left [ x \right ]=W\left [ x \right ]\)将其变形得\(d\left [ S_{i} \right ]=d\left [ x \right ]+W\left [ x \right ]\)。(\(d\left [ i \right ]\)表示i结点在树上的深度)这个式子可以抽象为在\(S_{i}\)到\(lca(S_{i},T_{i})\)的路径上的所有点都增加了一个类型为\(d\left [ x \right ]+W\left [ x \right ]\)的物品。最终这个点x的观察员能够观察到的人数就是这个点的类型为\(d\left [ x \right ]+W\left [ x \right ]\)物品数的和。另一条链的关系可以类似得到。
具体到实现中,有如下几点需要注意。
1 为了高效的对一条路径上的点修改,可以在树上对点差分,配合LCA的倍增算法可以实现O(nlogn)的复杂度。
2 本题最后对物品数求和的过程是动态开点的权值线段树的裸题。但是在这道题目中直接使用权值线段树会爆空间。仔细观察所求的值,会发现这个值具有区间可加性,意味着可以在dfs进入某棵子树时维护两个变量val1和val2分别代表两段上的答案,在对整棵子树结束访问时重新计算val1和val2的差值,就是这棵子树对答案的贡献。在代码中,用了c数组进行计数。
3 玩家i路径上的另一段,也就是\(lca(S_{i},T_{i})\)到\(T_{i}\)的部分可能会出现c数组下标为负数的情况,所以这里要进行数组下标平移或者离散化,这里代码中用的是数组下标平移的方式。
代码如下/* */ #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<set> #include<map> #include<queue> #include<stack> #include<vector> #include<cstring> #include<cstdlib> using namespace std; typedef long long ll; typedef pair<int,int>pii; const int maxn=300000+5; const int INF=0x3f3f3f3f; int n,m; struct node { int from,to; } edge[maxn*2]; int t,head[maxn],tot=0,ans[maxn],fa[maxn][20],d[maxn],v[maxn],c1[maxn*2],c2[maxn*2],w[maxn]; vector<int>a1[maxn],a2[maxn],b1[maxn],b2[maxn]; void add(int u,int v) { edge[++tot].to=v; edge[tot].from=head[u]; head[u]=tot; } void bfs() { queue<int>q; q.push(1); d[1]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=head[x]; i!=-1; i=edge[i].from) { int y=edge[i].to; if(!d[y]) { q.push(y); d[y]=d[x]+1; fa[y][0]=x; for(int j=1; j<=t; j++) { fa[y][j]=fa[fa[y][j-1]][j-1]; } } } } } int lca(int x,int y) { if(d[x]>d[y]) swap(x,y); for(int i=t; i>=0; i--) { if(d[fa[y][i]]>=d[x]) { y=fa[y][i]; } } if(x==y) return x; for(int i=t; i>=0; i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } return fa[x][0]; } void dfs(int x) { v[x]=1; int val1=c1[w[x]+d[x]],val2=c2[w[x]-d[x]+n]; for(int i=head[x]; i!=-1; i=edge[i].from) { int y=edge[i].to; if(!v[y]) { dfs(y); } } for(int i=0;i<a1[x].size();i++) c1[a1[x][i]]++; for(int i=0;i<b1[x].size();i++) c1[b1[x][i]]--; for(int i=0;i<a2[x].size();i++) c2[a2[x][i]+n]++; for(int i=0;i<b2[x].size();i++) c2[b2[x][i]+n]--; ans[x]+=c1[d[x]+w[x]]-val1+c2[w[x]-d[x]+n]-val2; } int main() { ios::sync_with_stdio(false); //freopen("天天爱跑步.in","r",stdin); memset(head,-1,sizeof(head)); cin>>n>>m; t=(int)(log(n)/log(2))+1; int u,v; for(int i=1; i<=n-1; i++) { cin>>u>>v; add(u,v); add(v,u); } bfs(); int x,y; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=m;i++){ cin>>x>>y; int z=lca(x,y); a1[x].push_back(d[x]); b1[fa[z][0]].push_back(d[x]); a2[y].push_back(d[x]-2*d[z]); b2[z].push_back(d[x]-2*d[z]); } dfs(1); for(int i=1;i<=n;i++){ cout<<ans[i]<<" "; } return 0; }
- 1
信息
- ID
- 1077
- 难度
- 2
- 分类
- (无)
- 标签
- 递交数
- 25
- 已通过
- 20
- 通过率
- 80%
- 上传者