为知笔记导入wordpress班级优化大师使用心得

题意：一棵树节点编号为1具有n种不同物种的演化树上。物种i将遗传信息向下传递到物种j会产生dij的遍历。dij是一个长为l的01串。变异程度duv为u到v简单路径上的所有编译信息的异或和。基因多样性定义为

分析：计算Di的遗传信息，用dfs将遗传信息传给儿子们，根据公式可得当m为奇数，除了第一个数和最后一个数是奇数，其它都是偶数，偶数异或为0；当m为偶数时，除了第一个数和最后一个数是偶数，其它都是奇数。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
bitset<100>d[N];
vector<int>edg[N]; 
void dfs(int u){for(int i=0;i<edg[u].size();i++){//儿子 int v=edg[u][i];d[v]^=d[u];dfs(v);}
}
void sol(){ll n,m,l;cin>>n>>m>>l;int u,v;for(int i=1;i<n;i++){cin>>u>>v>>d[v];edg[u].push_back(v);}dfs(1);vector<int>a(m);for(int i=0;i<m;i++)cin>>a[i];bitset<100>ans=0;if(m&1) {ans=d[a[0]]^d[a[m-1]];}else{for(int i=1;i<m-1;i++){ans^=d[a[i]];}}cout<<ans.to_string().substr(100-l,l)<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t=1;while(t--)sol();return 0;
}