题解 BZOJ4919 【大根堆】

题面：传送门。

老师说今天要考一道线段树合并，然后。。。然后这道题我就GG了。（当然可以用线段树合并写，只是比较复杂）

有人赛时想了个贪心，然后被机房巨佬hack了，结果在hack的过程中巨佬想出了正解。。。

贪心思路：

对于一个节点，取右边的（大一点的）肯定更优。

（其实很好hack啊，随便搞一条链就可以了）

AC思路：

对于每个节点，像LIS那样找子节点中大于它的最小的，然后替换掉，这样肯定是最优的。

于是这道题可以看做拓展到树上的LIS，

于是我们每个节点搞一个set，然后一路往上启发式合并就可以了。

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <set>

 4

 5 using namespace std;

 6

 7 namespace StandardIO {

 8

 9     template<typename T>inline void read (T &x) {

10         x=0;T f=1;char c=getchar();

11         for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;

12         for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';

13         x*=f;

14     }

15

16     template<typename T>inline void write (T x) {

17         if (x<0) putchar('-'),x*=-1;

18         if (x>=10) write(x/10);

19         putchar(x%10+'0');

20     }

21

22 }

23

24 using namespace StandardIO;

25

26 namespace Solve {

27

28     const unsigned int N=200001;

29

30     unsigned int n;

31     unsigned int val[N];

32     unsigned int cnt;

33     unsigned int head[N];

34     struct node {

35         unsigned int to,next;

36     } edge[N<<1];

37     multiset<unsigned int> s[N];

38

39     inline void add (unsigned int a,unsigned int b) {

40         edge[++cnt].to=b,edge[cnt].next=head[a],head[a]=cnt;

41     }

42     inline void merge (unsigned int u,unsigned int v) {

43         if (s[u].size()<s[v].size()) {

44             swap(s[u],s[v]);

45         }

46         for (register multiset<unsigned int>::iterator i=s[v].begin(); i!=s[v].end(); ++i) {

47             s[u].insert(*i);

48         }

49         s[v].clear();

50     }

51     void dfs (unsigned int now) {

52         for (register int i=head[now]; i; i=edge[i].next) {

53             dfs(edge[i].to);

54             merge(now,edge[i].to);

55         }

56         multiset<unsigned int>::iterator place=s[now].lower_bound(val[now]);

57         if (place!=s[now].end()) s[now].erase(place);

58         s[now].insert(val[now]);

59     }

60

61     inline void solve() {

62         read(n);

63         for (register unsigned int i=1; i<=n; ++i) {

64             unsigned int tmp;

65             read(val[i]),read(tmp);

66             if (tmp) add(tmp,i);

67         }

68         dfs(1);

69         write(s[1].size());

70     }

71

72 }

73

74 using namespace Solve;

75

76 int main () {

77     solve();

78 }

巴特西

题解 BZOJ4919 【大根堆】

最新文章

热门文章