当前位置:网站首页>B-杰哥的树(状压树形dp)
B-杰哥的树(状压树形dp)
2022-07-06 12:18:00 【朴小明】
链接:杰哥的树
题意:
给定一棵树,边权 是 这六个字符,求不同的路径数,要求路径上的字符都恰好出现偶数次。
做法:
只关心奇偶,那么一个字符就可有两个状态——1代表奇数个,0代表偶数个,要想同时表示六个字符是奇数还是偶数,就可用0~63来表示。
定义 为以第 个节点为起点,状态为 有多少路径数量,如果 的儿子是 ,当前字符是 ,那么 ,除了由儿子的状态转移而来,还会有新的状态,不继承儿子的状态, 到 的这条边也可单独作为一个状态,则当时, 。
还要考虑点作为中间节点的情况,这个简单,由 计算即可。
代码:
struct tree
{
int y, val;
};
vector<tree> v[N];
int f[N][1ll << 6];
int ans;
void dfs(int x, int fa)
{
f[x][0] = 0;
for (auto tt : v[x])
{
int y = tt.y, val = tt.val;
if (y == fa) continue;
dfs(y, x);
for (int i = 0; i < (1ll << 6); i++)
{
f[x][i] += f[y][i ^ (1ll << val)];
if (i == (1ll << val)) f[x][i]++; //不能乱加1,之所以加1,是因为定义x这个点只出一条边
}
}
ans += f[x][0];
int sum = 0;
for (auto tt : v[x])
{
int y = tt.y, val = tt.val;
if (y == fa) continue;
for (int i = 0; i < (1ll << 6); i++)
{
int x1 = f[x][i] - f[y][i ^ (1ll << val)] - (i == (1ll << val));
int x2 = f[y][i ^ (1ll << val)] + (i == (1ll << val));
sum += x1 * x2;
}
}
ans += sum / 2;
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n - 1; i++)
{
int x, y;
char c;
scanf("%lld%lld", &x, &y);
cin >> c;
v[x].emplace_back(tree{y, c - 'a'});
v[y].emplace_back(tree{x, c - 'a'});
}
dfs(1, 0);
cout << ans << "\n";
}
边栏推荐
- Standardized QCI characteristics
- Leetcode 30. Concatenate substrings of all words
- Blue Bridge Cup microbial proliferation C language
- Database specific interpretation of paradigm
- [cloud native and 5g] micro services support 5g core network
- [Yann Lecun likes the red stone neural network made by minecraft]
- Case ① | host security construction: best practice of 3 levels and 11 capabilities
- [infrastructure] deployment and configuration of Flink / Flink CDC (MySQL / es)
- Classic 100 questions of algorithm interview, the latest career planning of Android programmers
- js实现力扣71题简化路径
猜你喜欢
5. 无线体内纳米网:十大“可行吗?”问题
Standardized QCI characteristics
redisson bug分析
Leetcode 30. Concatenate substrings of all words
Node.js: express + MySQL实现注册登录,身份认证
Li Kou 101: symmetric binary tree
Selenium advanced operations
Information System Project Manager - Chapter VIII project quality management
Node. Js: express + MySQL realizes registration, login and identity authentication
22-07-05 七牛云存储图片、用户头像上传
随机推荐
Vscode debug run fluent message: there is no extension for debugging yaml. Should we find yaml extensions in the market?
Monthly report of speech synthesis (TTS) and speech recognition (ASR) papers in June 2022
Oceanbase Community Edition OBD mode deployment mode stand-alone installation
[network planning] Chapter 3 data link layer (4) LAN, Ethernet, WLAN, VLAN
深入浅出,面试突击版
The "white paper on the panorama of the digital economy" has been released with great emphasis on the digitalization of insurance
Introduction of Xia Zhigang
Node. Js: express + MySQL realizes registration, login and identity authentication
腾讯云数据库公有云市场稳居TOP 2!
VMware virtual machine cannot open the kernel device "\.\global\vmx86"
A5000 vGPU显示模式切换
Method keywords deprecated, externalprocname, final, forcegenerate
Wechat applet common collection
[play with Linux] [docker] MySQL installation and configuration
方法关键字Deprecated,ExternalProcName,Final,ForceGenerate
爬虫(14) - Scrapy-Redis分布式爬虫(1) | 详解
MySQL must know and learn
In simple terms, interview surprise Edition
Standardized QCI characteristics
BUUCTF---Reverse---easyre