2019icpc西安邀请赛 J And And And (树形dp)

你的名字 2021-10-30 02:38 462阅读 0赞

题目链接:https://nanti.jisuanke.com/t/39277

题意:给出一棵有边权的树,求所有简单路径包含异或和为0的简单路径的总数和。

思路:

  首先,对于异或为0这一限制,我们通过dfs得到根节点到所有点的路径上的异或和val[i],如果两个结点的val值相等,说明他们之间的路径满足异或和为0。sz [i]为以i为根的子树 的大小。

  其次,对于满足异或和为0的两个点u、v,分两种情况考虑:

    1. u、v在不同链上,这一条路径的贡献值为sz[u]*sz[v],通过map记录每一种权值的size和即可得到。我们先将所有点这样处理一遍。

    2. u、v在一条链上,这一条路径的贡献值为(n-sz[u1])*sz[v],u1是u与v这一条链上u的第一个子结点。因为上一步我们把所有情况加上了,所以要先减去sz[u]*sz[v],通过mp1来记录同一条链上异或值为val的size和,因为是记录同一条链,所以当处理完一个结点的所有子结点时要回溯更新,即减去前面加的size。减了之后加上(n-sz[u1])*sz[v],通过mp2来记录该信息,每处理完一个子结点时回溯更新,因为已经不在一条链上。

AC代码:

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<unordered_map>
  4. using namespace std;
  5. const int maxn=1e5+5;
  6. const int MOD=1e9+7;
  7. typedef long long LL;
  8. typedef unordered_map<LL,LL> ump;
  9. struct node{
  10. int v,nex;
  11. LL w;
  12. }edge[maxn];
  13. int n,head[maxn],cnt,sz[maxn];
  14. LL val[maxn],ans;
  15. ump sum,mp1,mp2;
  16. void adde(int u,int v,LL w){
  17. edge[++cnt].v=v;
  18. edge[cnt].w=w;
  19. edge[cnt].nex=head[u];
  20. head[u]=cnt;
  21. }
  22. void dfs1(int u,LL va){
  23. val[u]=va,sz[u]=1;
  24. for(int i=head[u];i;i=edge[i].nex){
  25. int v=edge[i].v;
  26. LL w=edge[i].w;
  27. dfs1(v,va^w);
  28. sz[u]+=sz[v];
  29. }
  30. }
  31. void dfs2(int u){
  32. ans=(ans+sum[val[u]]*sz[u])%MOD;
  33. sum[val[u]]=(sum[val[u]]+sz[u])%MOD;
  34. for(int i=head[u];i;i=edge[i].nex)
  35. dfs2(edge[i].v);
  36. }
  37. void dfs3(int u){
  38. ans=(ans-mp1[val[u]]*sz[u]+mp2[val[u]]*sz[u]+MOD)%MOD;
  39. mp1[val[u]]=(mp1[val[u]]+sz[u])%MOD;
  40. for(int i=head[u];i;i=edge[i].nex){
  41. int v=edge[i].v;
  42. LL w=edge[i].w;
  43. mp2[val[u]]=(mp2[val[u]]+n-sz[v]+MOD)%MOD;
  44. dfs3(v);
  45. mp2[val[u]]=(mp2[val[u]]-n+sz[v]+MOD)%MOD;
  46. }
  47. mp1[val[u]]=(mp1[val[u]]-sz[u]+MOD)%MOD;
  48. }
  49. int main(){
  50. scanf("%d",&n);
  51. for(int i=2;i<=n;++i){
  52. int u;LL w;
  53. scanf("%d%lld",&u,&w);
  54. adde(u,i,w);
  55. }
  56. dfs1(1,0);
  57. dfs2(1);
  58. dfs3(1);
  59. printf("%lld\n",ans);
  60. return 0;
  61. }

转载于:https://www.cnblogs.com/FrankChen831X/p/11371882.html

发表评论

表情:
评论列表 (有 0 条评论,462人围观)

还没有评论,来说两句吧...

相关阅读

    相关 and or php,AND OR

    \\ AND OR 上面是基础的Where语句,下面看一下复杂一点的 你可以使用"AND" 或 "OR" 来拼接非常复杂的SQL语句 ~~~ namespace Act