“华为杯”杭州电子科技大学2023新生编程大赛---树

题目链接

Problem Description

给定一棵包含 n 个节点的带边权的树，树是一个无环的无向联通图。定义 xordist(u,v) 为节点 u 到 v 的简单路径上所有边权值的异或和。

有 q 次询问，每次给出 `l r x`，求 ∑ri=lxordist(i,x) 的值。

Input

测试点包含多组数据。第一行包含一个整数 T（1≤T≤10），表示数据组数。每组数据的输入格式如下：
第一行包含一个整数 n（1≤n≤105），表示节点的个数。
接下来 n−1 行，每行包含三个整数 u、v 和 w（1≤u,v≤n，0≤w<230），表示 u 和 v 之间存在一条权值为 w 的无向边。保证输入是一棵树。
接下来一行，包含一个整数 q（1≤q≤105），表示询问的次数。
接下来 q 行，每行包含三个整数 l、r 和 x（1≤l≤r≤n，1≤x≤n），分别表示每次询问的信息，其含义已在上文说明。

Output

每组数据包含 q 行，每行一个整数，表示每次询问的答案。

题意：

定义了一个函数  xordist(u,v) 为节点 u 到 v 的简单路径上所有边权值的异或和。

给你多次询问，求有 q 次询问，每次给出 l， r， x，求  xordist(i,x) 的值。

思路：

首先可以知道，我们任意选一点为根 root 往下递归异或就可以得到 f [ i ](root 到 i 的路径异或值 ），那么  l 到 r 的路劲异或值可以由 f [ l ] ^ f [ r ]得出；

那么如何计算答案呢，就是用 f [ l ]~f [ r ] 分别异或f [ x ] 相加即可，但是1e5级别的询问显然时间复杂度不可以接受，然后我们就行有什么可以快速算出 l ~ r  的贡献呢，这时候就看思维发不发散了，这里可以想到用前缀和；

(当然不是异或前缀和，异或不满足分配律，比如 (2^3+2^3+4^3)!=8^3

所以是另一种 ：计算1~n , f [ i ] 2进制的每一位1和0的前缀和，

那么答案就是，对f [ x ] 的每一位的贡献计算，比如f [ x ] 第2位是0，那么根据异或1异或0才有贡献， 贡献就是 pow( 2 , i (第几位) ）*( sum1[ r ][ i ]-sum1[ l-1 ][ i ] );

复杂度位1e5*30，显然可以接受

完毕

int n;
int f[N];
vector<PII> g[N];
void dfs(int u, int fa)
{for (auto ed : g[u]){if (ed.xx == fa)continue;f[ed.xx] = f[u] ^ ed.yy;dfs(ed.xx, u);}
}
int qpow(int a, int b)
{int res = 1;while (b){if (b & 1)res = res * a;a = a * a;b >>= 1;}return res;
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++){g[i].clear();f[i] = 0;}int root = inf;for (int i = 1; i <= n - 1; i++){int a, b, c;cin >> a >> b >> c;g[a].pb({b, c});g[b].pb({a, c});root = min({a, b, root});}dfs(root, -1);vector<vector<int>> sum1(n + 2, vector<int>(32));vector<vector<int>> sum0(n + 2, vector<int>(32));for (int i = 1; i <= n; i++){for (int j = 0; j <= 29; j++){int x = (f[i] >> j & 1);if (x)sum1[i][j]++;elsesum0[i][j]++;sum1[i][j] += sum1[i - 1][j];sum0[i][j] += sum0[i - 1][j];}}int q;cin >> q;while (q--){int l, r, x;cin >> l >> r >> x;int ans = 0;for (int i = 0; i <= 29; i++){int t = (f[x] >> i & 1);if (t)ans += qpow(2, i) * (sum0[r][i] - sum0[l - 1][i]);elseans += qpow(2, i) * (sum1[r][i] - sum1[l - 1][i]);}cout << ans << endl;}
}
signed main()
{Yshanqian;int T;T = 1;cin >> T;for (int cases = 1; cases <= T; ++cases){// cout<<"Case #"<<cases<<": ";solve();}return 0;
}