時間限制1秒?內存限制64M

題目描述：

「我們大部分的煩惱，是來自于夢想另一種有可能的人生。把希望寄托于自己的可能性這種不能指望的東西，正是萬惡的根源。」

時間突然停止。

我獲得了可以在平行世界中穿梭的能力。

宇宙中存在著無數的平行世界，這些世界組成了一個樹形的結構，每個世界有一個編號和一個幸福度。

?

每當我做出選擇時，世界會分裂成若干個新的世界。選擇會導致幸福度的變化。根據選擇的不同，在新的世界里，我可能會變的更加幸福，或者更加不幸。

出于某些原因，我只能在處于相同時間的世界內穿梭，而且只能在由若干個時間單位前的世界分裂來的世界中穿梭。

我要在平行世界中找到一個最幸福的世界，在那里繼續生活下去。然而真的存在這樣的世界嗎？

輸入格式：

第一行，一個整數，表示一共有個世界。

接下來行，每行三個整數,,?. 表示號世界下一個時間單位內會走向號世界，幸福度會變化。(,?)

接下來一行，一個整數，表示接下來有Q個詢問。

接下來行，每行兩個整數,?。表示現在身處號世界，允許穿梭到從個時間單位前分裂的所有世界。?，??。

數據保證，1號世界是根節點，且1號節點的幸福度是。

輸出格式：

行，每行一個整數。第的整數表示第個詢問中，能獲得的最大幸福度。

樣例輸入：

8

1 2 1

2 3 3

1 4 2

1 5 -2

5 6 3

5 7 4

5 8 -2

3

6 1

6 2

5 1

樣例輸出:

2

4

2

樣例解釋：

對于第二個詢問(6, 2)，6號世界2個時間單位前的世界是1號世界，1號世界分裂的所有世界中，與6號世界處在相同時間的是3號、6號、7號、8號世界，其中幸福度最高的是3號世界(0 + 1 + 3 = 4)。

題目大意：

? ? ? ? ? ? ? 一棵有根樹，每個節點有一個權值，現在有若干個詢問，對于每一個詢問（x，y），求與x節點有相同深度且具有相同第y級祖先的所有節點中，權值的最大值。

解題思路：

? ? ? ? ? ?用類似在線倍增lca的思路，nlogn預處理，可以在logn內求出他的y級祖先。

? ? ? ? ? ?相同深度而且有某個公共y級祖先的節點的bfs序是連續的，如果獲得了bfs序的區間，可以用rmq求出這個區間節點中的最大權值。

? ? ? ? ? ?先求出所有點的bfs序，構建這些節點的st，然后二分求出區間的左端點和右端點（隨著bfs序的增大他們的y級祖先的bfs序也在增大）每次求祖先logn的，因此查詢的復雜度是（logn)^2的，總的復雜度o(qlognlogn)

#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<cmath> using namespace std; const int maxn = 100050; const double eps = 1e-6; int p[maxn][55], head[maxn], tot, val[maxn], vis[maxn], bfsxu, pos[maxn], spos[maxn], mm[maxn]; int maxx[maxn][55]; struct node {int from, to, next, val; }e[maxn]; void init() {tot = 0; bfsxu = 1; pos[1] = 1; spos[1] = 1;memset(head, -1, sizeof(head));memset(vis, 0, sizeof(vis));memset(val, 0, sizeof(val));memset(p, -1, sizeof(p)); } void add(int u, int v, int w) {e[tot].from = u;e[tot].to = v;e[tot].next = head[u];e[tot].val = w;head[u] = tot++; } void dfs(int u) {vis[u] = 1;for (int i = head[u]; ~i; i = e[i].next){int v = e[i].to;if (!vis[v]){p[v][0] = u;dfs(v);}} } void rmq(int n) {for (int j = 1; (1 << j) <= n; j++)for (int i = 1; i <= n; i++)if (~p[i][j - 1])p[i][j] = p[p[i][j - 1]][j - 1]; } void st(int n) {mm[0] = -1;for (int i = 1; i <= n; i++){mm[i] = ((i&(i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];maxx[i][0] = val[pos[i]];}for (int j = 1; j <= mm[n]; j++)for (int i = 1; i + (1 << j) - 1 <= n; i++)maxx[i][j] = max(maxx[i][j - 1], maxx[i + (1 << (j - 1))][j - 1]); } int lca(int x, int y) {int pa = x;while (y&&pa != -1){int low = y&(-y);pa = p[pa][mm[low]];y -= low;}if (pa == -1)return 0;return pa; } int solve(int x, int y) {int k = mm[y - x + 1];return max(maxx[x][k], maxx[y - (1 << k) + 1][k]); } int main() {int n, x, y, z, q;while (~scanf("%d", &n)){init();for (int i = 1; i < n; i++){scanf("%d%d%d", &x, &y, &z);add(x, y, z);}dfs(1);rmq(n);queue<int>que;que.push(1);while (!que.empty()){int u = que.front(); que.pop();for (int i = head[u]; ~i; i = e[i].next){int v = e[i].to;val[v] = val[e[i].from] + e[i].val;pos[++bfsxu] = v; spos[v] = bfsxu;que.push(v);}}st(n);scanf("%d", &q);while (q--){scanf("%d%d", &x, &y);int fa = lca(x, y), ll, rr;int l = 1, r = spos[x];while (l<r){int mid = (l + r) / 2;if (spos[lca(pos[mid], y)] < spos[fa])l = mid + 1;else r = mid;}ll = l;l = spos[x], r = n;while (l<r){int mid = (l + r) / 2;if (spos[lca(pos[mid], y)]>spos[fa])r = mid - 1;else l = mid;if (r == l + 1){if (spos[lca(pos[r], y)] == spos[fa])l = r;else r = l;}}rr = l;printf("%d\n", solve(ll, rr));}}return 0; }

總結

以上是生活随笔為你收集整理的四叠半神话大系（bfs序+st+在线倍增+二分）(北理16校赛）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。