[USACO17JAN]Promotion Counting 題解

前言

巨佬說:要有線段樹，結果蒟蒻打了一棵樹狀數組...
想想啊，奶牛都開公司當老板了，我還在這里碼代碼，太失敗了。
話說奶牛開個公司老板不應該是FarmerJohn嗎？

題解

剛看到這道題的時候竟然沒有想到深搜，然后仔細一想，發現果然要用深搜。
但是這個樹形結構怎么維護是一個問題？難道打個歐拉序...
其實做法非常簡單，首先按照套路我們把牛的能力值離散化(由于沒有相同的值，所以這個離散化非常簡單)。
然后重點來了，建立一個維護某一能力值牛的個數的樹狀數組。
我們深搜到一個點的時候，我們不希望計算的部分是比它大的祖先，而希望計算的部分是比它大的兒子。
于是我們在搜到這個點的時候將它的答案減去當前樹狀數組里能力值比它大的牛的個數(減去祖先部分)，然后我們搜索它的所有兒子。
搜索完成后，我們將它的答案加上當前樹狀數組里比它大的牛的個數(加上兒子和祖先部分)。所以一加一減只剩下兒子的部分。
然后輸出我們的答案數組，就AC了。

代碼

#include <cstdio>
#include <algorithm>
#define ll long longusing namespace std;ll read(){ll x = 0; int zf = 1; char ch = ' ';while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();if (ch == '-') zf = -1, ch = getchar();while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}struct Edge{int to, next;
} edges[200005];int head[100005], edge_num = 0;void addEdge(int from, int to){edges[++edge_num] = (Edge){to, head[from]};head[from] = edge_num;
}int n;namespace FenTree{#define lowbit(x) (x&-x)int BIT[100005];int query(int i){int res = 0;for ( ; i; i -= lowbit(i)) res += BIT[i]; return res;}void add(int i){for ( ; i <= n; i += lowbit(i)) ++BIT[i];}#undef lowbit
};using namespace FenTree;int p[100005], dy[100005];
int ans[100005];bool Comp(const int &a, const int &b){return p[a] > p[b];};void DFS(int u, int fa){ans[u] -= query(p[u]);for (int c_e = head[u]; c_e; c_e = edges[c_e].next)if (edges[c_e].to != fa) DFS(edges[c_e].to, u);ans[u] += query(p[u]); add(p[u]);
}int main(){n = read();for (int i = 1; i <= n; ++i) p[i] = read(), dy[i] = i;sort(dy + 1, dy + n + 1, Comp);for (int i = 1; i <= n; ++i) p[dy[i]] = i;for (int i = 2; i <= n; ++i){int x = read(); addEdge(i, x), addEdge(x, i);}DFS(1, 1);for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);return 0;
}