【题解】$test0628$ 仓库选址

题目描述

喵星系有 n$n$ 个星球，星球以及星球间的航线形成一棵树。

从星球 a$a$ 到星球 b$b$ 要花费 [dis(a,b)XorM]$[dis(a,b)XorM]$秒。（dis(a,b)$dis(a,b)$ 表示 a,b$a,b$ 间的航线长度，Xor$Xor$ 为位运算中的异或）

为了给仓库选址，pf想知道，星球 i$i$（1≤i≤n$1\le i\le n$）到其他所有星球花费的时间之和。

---

Solution$Solution$

这道题其实一点都不难啊！！！就是一个裸换根 dp$dp$ 加一点点二进制小技巧，网上的题解太高大上了，蒟蒻瑟瑟发抖 \kk$\text{kk}$

首先发现，若 m=0$m=0$ 那么就是个裸换根 dp$dp$

具体的就不写了，连我这种蒟蒻都会那各位dalao肯定都会！（主要是懒

考虑加上异或 m$m$

观察数据范围，发现 m<=15$m<=15$，也就是说，异或了 m$m$ 顶多修改二进制下后面 4$4$ 位

于是另外设 g[i][j]$g[i][j]$ 表示到 i$i$ 的点的路径中，有多少条是二进制下后面 4$4$ 位为 j$j$ 的

然后我们就只要在最最最后，加上这样一句，

ans[i]+=((j xor m) − j) ∗ g[i][j]$$ans[i]+=((jxorm)-j)\ast g[i][j]$$

就是答案啦！是不是超简单！！

这一句话是什么意思呢？

假设有一条到 i$i$ 的路径长为 x$x$，x$x$ 的二进制下后 4$4$ 位为 j$j$ ，由于顶多更改最后 4$4$ 位，所以只有 j$j$ 部分被更改

在题意里要加进去的贡献应该是 j xor m$jxorm$ ，但是现在 ans[i]$ans[i]$ 里存的是 j$j$ ，所以我们要加上一个 j xor m$jxorm$ 减去一个 j$j$

简单来说就是这样

j+(j xor m − j) = j xor m$$j+(jxorm-j)=jxorm$$

那么这优化在了哪里呢？

实际上这就相当于我们对于每一条路径都先求出长度，然后更改，但是这样就是 O(n2)$O(n^2)$ 了，于是我们把所有能够一起更改的（也就是后四位一样的）统计一下，在最后一起更改，复杂度就降为 O(nm)$O(nm)$ 辣！

再次感慨一下这道题做法，太！神！力！

完结撒花✿✿ヽ(°▽°)ノ✿

---

Code$Code$

好吧原来这道题难点在于代码实现？？？重构了代码的蒟蒻哭力——

可能代码和上面讲的有些偏差，具体代码里解释

#include<bits/stdc++.h>
#define F(i, x, y) for(int i = x; i <= y; ++ i)
using namespace std;
int read();



语言
方法


1661
l63sU

RLJ9S

俪仙「私照」18勿扰「美艳绝伦」

2915
2008/07/23 08:13:12
const int N = 1e5 + 5;
const int mod = 16;
int n, m, u, v, e;
int g[N][16], dp[N];
int head[N], cnt, ver[N << 1], edge[N << 1], nxt[N << 1];
void add(int x, int y, int z){ver[++ cnt] = y, edge[cnt] = z, nxt[cnt] = head[x], head[x] = cnt;}
void dfs1(int x, int fa)
{
   g[x][0] = 1;
   for(int i = head[x]; i; i = nxt[i])
      if(ver[i] != fa)
      {
         dfs1(ver[i], x), dp[x] += dp[ver[i]];//这里的dp求的是i子树到i的距离和
         F(j, 0, 15) g[x][(j + edge[i]) % mod] += g[ver[i]][j], dp[x] += g[ver[i]][j] * edge[i];
         /*对于当前这条边，会被贡献size[son]这么多次，而g[son]的总和就是size[son]*/
      }
}
void dfs2(int x, int fa)
{
   for(int i = head[x]; i; i = nxt[i])
      if(ver[i] != fa)
      {
         int tmp[16] = {0}, size = 0;
         F(j, 0, 15) 
            tmp[(j + edge[i]) % mod] += g[x][j] - g[ver[i]][((j - edge[i]) % mod + mod) % mod], size += g[ver[i]][j];
            /*由fa往i转移时要用g[fa]减掉那些i子树中的链*/
         dp[ver[i]] = dp[x] + (n - size * 2)  * edge[i];
         /*可以看成n-size-size，n-size是有这么多个点要经过这条边，还要减一个size是因为dp[x]中包含了size条这个边，要减去*/
         F(j, 0, 15) g[ver[i]][j] += tmp[j];
         dfs2(ver[i], x);
      }
}
int main()
{
   n = read(), m = read();
   F(i, 1, n - 1) u = read(), v = read(), e = read(), add(u, v, e), add(v, u, e);
   dfs1(1, 0), dfs2(1, 0);
   F(i, 1, n) F(j, 0, 15) dp[i] += ((j ^ m) - j) * (g[i][j] - (j == 0));
   F(i, 1, n) printf("%d\n", dp[i]);
   return 0;
}
/*--------------- Bn_ff 2020.7.2 ybt1771 ---------------*/
int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}