社区网站建设难点,如何做好seo基础优化,音乐外链网站,宁波网站建设公司排名题目链接
Problem Description
给定一棵包含 n 个节点的带边权的树#xff0c;树是一个无环的无向联通图。定义 xordist(u,v) 为节点 u 到 v 的简单路径上所有边权值的异或和。 有 q 次询问#xff0c;每次给出 l r x#xff0c;求 ∑rilxordist(i,x) 的值。
Input
测试…题目链接
Problem Description
给定一棵包含 n 个节点的带边权的树树是一个无环的无向联通图。定义 xordist(u,v) 为节点 u 到 v 的简单路径上所有边权值的异或和。 有 q 次询问每次给出 l r x求 ∑rilxordist(i,x) 的值。
Input
测试点包含多组数据。第一行包含一个整数 T1≤T≤10表示数据组数。每组数据的输入格式如下 第一行包含一个整数 n1≤n≤105表示节点的个数。 接下来 n−1 行每行包含三个整数 u、v 和 w1≤u,v≤n0≤w230表示 u 和 v 之间存在一条权值为 w 的无向边。保证输入是一棵树。 接下来一行包含一个整数 q1≤q≤105表示询问的次数。 接下来 q 行每行包含三个整数 l、r 和 x1≤l≤r≤n1≤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^32^34^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];
vectorPII 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);vectorvectorint sum1(n 2, vectorint(32));vectorvectorint sum0(n 2, vectorint(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){// coutCase #cases: ;solve();}return 0;
}
