BZOJ4381 : [POI2015]Odwiedziny / Luogu3591[POI2015]ODW

Solution

在步伐$pace$比较小的时候，我们发现用前缀和直接维护会很快

而在$pace$比较大的时候，则暴力往上跳会最优

设$blo= sqrt{N}$

若$pace<=blo$，则利用前缀和更新,

预处理复杂度$O(N sqrt{N})$，查询复杂度$O(1)$

若$pace>blo$，则利用树剖逐渐往上跳

总共要跳$N/pace$次，一共有$logN$条轻重链，复杂度为$O(logN+ sqrt{N})$

代码实现比较麻烦，我常数写的还很差，水平低啊QAQ

Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cmath>
  5 #define rd read()
  6 #define N 50005
  7 #define M 240
  8 #define R register
  9 using namespace std;
 10 
 11 int n, blo, a[N], b[N], f[N][M], sum[N][M];
 12 int fa[N], dep[N], top[N], sz[N], son[N], id[N], idf[N], cnt;
 13 int head[N], tot;
 14 
 15 struct edge {
 16     int nxt, to;
 17 }e[N << 1];
 18 
 19 inline char nc(){
 20     static char buf[100000], *p1=buf, *p2=buf;
 21     return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
 22 }
 23 inline int read(){
 24     char ch = nc();int sum = 0;
 25     while(!(ch >= '0' && ch <= '9')) ch = nc();
 26     while(ch >= '0' && ch <= '9') sum = sum * 10 + ch - 48, ch = nc();
 27     return sum;
 28 }
 29 
 30 inline void add(int u, int v) {
 31     e[++tot].to = v;
 32     e[tot].nxt = head[u];
 33     head[u] = tot;
 34 }
 35 
 36 inline void sw(int &A, int &B) {
 37     A ^= B; B ^= A; A ^= B;
 38 }
 39 
 40 inline void dfs1(R int u) {
 41     sz[u] = 1;
 42     for (R int i = head[u]; i; i = e[i].nxt) {
 43         R int nt = e[i].to;
 44         if (nt == fa[u]) continue;
 45         f[nt][1] = fa[nt] = u;
 46         dep[nt] = dep[u] + 1;
 47         dfs1(nt);
 48         sz[u] += sz[nt];
 49         if (sz[nt] > sz[son[u]])
 50             son[u] = nt;
 51     }
 52 }
 53 
 54 inline void dfs2(R int u) {
 55     idf[id[u] = ++cnt] = u;
 56     if (!son[u]) return;
 57     top[son[u]] = top[u];
 58     dfs2(son[u]);
 59     for (R int i = head[u]; i; i = e[i].nxt) {
 60         R int nt = e[i].to;
 61         if (nt == fa[u] || nt == son[u]) continue;
 62         top[nt] = nt;
 63         dfs2(nt);
 64     }
 65 }
 66 
 67 inline int LCA(R int x, R int y) {
 68     for (;top[x] != top[y]; ) {
 69         if (dep[top[x]] < dep[top[y]]) sw(x, y);
 70         x = fa[top[x]];
 71     }
 72     if (dep[x] < dep[y]) sw(x, y);
 73     return y;
 74 }
 75 
 76 inline int work1(R int x, R int y, R int pace) {
 77     R int lca = LCA(x, y), len = dep[x] + dep[y] - 2 * dep[lca], res = 0;
 78     if (len % pace) {
 79         res += a[y];
 80         y = f[y][len % pace];
 81         len -= len % pace;
 82     }
 83     len = dep[x] - dep[lca];
 84     if (len % pace == 0) {
 85         res += sum[x][pace] - sum[lca][pace];
 86         res += sum[y][pace] - sum[lca][pace];
 87         res += a[lca];
 88         return res;
 89     }
 90     R int tmp = f[lca][pace - len % pace];
 91     res += sum[x][pace] - sum[tmp][pace];
 92     if (dep[y] < dep[lca]) return res;
 93     len = dep[y] - dep[lca];
 94     tmp = f[lca][pace - len % pace];
 95     res += sum[y][pace] - sum[tmp][pace];
 96     return res;
 97 }
 98 
 99 inline int up(R int x, R int d) {
100     R int y = top[x];
101     for (; x && dep[x] - dep[y] < d;) {
102         d -= dep[x] - dep[y] + 1;
103         x = fa[top[x]];
104         y = top[x];
105     }
106     if (!x) return 0;
107     return idf[id[x] - d];
108 }
109 
110 inline int work2(R int x, R int y, R int pace) {
111     R int lca = LCA(x, y), len = dep[x] + dep[y] - 2 * dep[lca], res = 0;
112     if (len % pace) {
113         res += a[y];
114         y = up(y, len % pace);
115         len -= len % pace;
116     }
117     len = dep[x] - dep[lca];
118     if (len % pace == 0) {
119         while (x && dep[x] > dep[lca])
120             res += a[x], x = up(x, pace);
121         while (y && dep[y] > dep[lca])
122             res += a[y], y = up(y, pace);
123         res += a[lca];
124         return res;
125     }
126     while (x && dep[x] > dep[lca])
127         res += a[x], x = up(x, pace);
128     while (y && dep[y] > dep[lca])
129         res += a[y], y = up(y, pace);
130     return res;
131 }
132 
133 int main()
134 {
135     n = rd; blo = sqrt(n);
136     for (R int i = 1; i <= n; ++i)
137         a[i] = rd;
138     for (R int i = 1; i < n; ++i) {
139         int u = rd, v = rd;
140         add(u, v); add(v, u);
141     }
142     dep[1] = 1; dfs1(1);
143     top[1] = 1; dfs2(1);
144     for (R int j = 2; j <= blo; ++j)
145         for (R int i = 1; i <= n; ++i)
146             f[i][j] = f[f[i][j - 1]][1];
147     for (R int j = 1; j <= blo; ++j)
148         for (R int i = 1; i <= n; ++i) 
149             sum[i][j] = a[i];
150     for (R int j = 1; j <= blo; ++j)
151         for (R int i = 1; i <= n; ++i) {
152             int x = idf[i];
153             sum[x][j] += sum[f[x][j]][j];
154         }
155     for (R int i = 1; i <= n; ++i) b[i] = rd;
156     for (R int i = 1; i < n; ++i) {
157         R int x = rd;
158         if (x <= blo) printf("%d
", work1(b[i], b[i + 1], x));
159         else printf("%d
", work2(b[i], b[i + 1], x));
160     }
161 }

View Code