2019icpc西安邀请赛 J And And And (树形dp)
2024-09-02 13:44:44
题目链接: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代码:
#include<cstdio>
#include<algorithm>
#include<unordered_map>
using namespace std; const int maxn=1e5+;
const int MOD=1e9+;
typedef long long LL;
typedef unordered_map<LL,LL> ump;
struct node{
int v,nex;
LL w;
}edge[maxn]; int n,head[maxn],cnt,sz[maxn];
LL val[maxn],ans;
ump sum,mp1,mp2; void adde(int u,int v,LL w){
edge[++cnt].v=v;
edge[cnt].w=w;
edge[cnt].nex=head[u];
head[u]=cnt;
} void dfs1(int u,LL va){
val[u]=va,sz[u]=;
for(int i=head[u];i;i=edge[i].nex){
int v=edge[i].v;
LL w=edge[i].w;
dfs1(v,va^w);
sz[u]+=sz[v];
}
} void dfs2(int u){
ans=(ans+sum[val[u]]*sz[u])%MOD;
sum[val[u]]=(sum[val[u]]+sz[u])%MOD;
for(int i=head[u];i;i=edge[i].nex)
dfs2(edge[i].v);
} void dfs3(int u){
ans=(ans-mp1[val[u]]*sz[u]+mp2[val[u]]*sz[u]+MOD)%MOD;
mp1[val[u]]=(mp1[val[u]]+sz[u])%MOD;
for(int i=head[u];i;i=edge[i].nex){
int v=edge[i].v;
LL w=edge[i].w;
mp2[val[u]]=(mp2[val[u]]+n-sz[v]+MOD)%MOD;
dfs3(v);
mp2[val[u]]=(mp2[val[u]]-n+sz[v]+MOD)%MOD;
}
mp1[val[u]]=(mp1[val[u]]-sz[u]+MOD)%MOD;
} int main(){
scanf("%d",&n);
for(int i=;i<=n;++i){
int u;LL w;
scanf("%d%lld",&u,&w);
adde(u,i,w);
}
dfs1(,);
dfs2();
dfs3();
printf("%lld\n",ans);
return ;
}
最新文章
- linux系统下重启tomcat的shell脚本
- Feature Flag
- android.content.Context 含义及使用
- reduce + Promise 顺序执行代码
- 用JavaScript(js)对时间格式化
- cf703A Mishka and Game
- [Ext JS 4] 实战之Grid, Tree Gird 添加按钮列
- linux上ln命令详细说明
- C#避免过长的IF和Switch分支的方法
- Webkit之资源加载
- warning: in-class initialization of non-static data member is a C++11 extension [-Wc++11-extensions]
- 实现去哪儿来回机票选择的view
- sqlzoo:2
- windows下面Nginx日志切割
- jmeter 写正则表达式
- 页面滚动图片等元素动态加载插件jquery.scrollLoading.js
- 给msde加装企业管理器
- 实验吧—安全杂项——WP之 你知道他是谁吗?
- mysql的一些 参数查询
- 工作总结 vue 城会玩