FilesExpand file tree

main

/

HLD.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

124 lines (95 loc) · 2.2 KB

main

/

HLD.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

124 lines (95 loc) · 2.2 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

// HLD implementation for max along a path in a tree

void dfs_size(int s,int p){

dis[s]=dis[p]+1;

// tin[s]=++cnt;

up[s][0]=p;

for(int i=1;i<21;i++){

up[s][i]=up[up[s][i-1]][i-1];//binary lifting

}

siz[s]=1;

int bigv=-1,bigc=-1;

for(auto el:graph[s]){

if(el==p)continue;

dfs_size(el,s);

siz[s]+=siz[el];

if(siz[el]>bigv){

bigv=siz[el];

bigc=el;

}

}

bigchild[s]=bigc;

}

int LCA(int u,int v){

if(dis[u]<dis[v]){

int temp=dis[v]-dis[u];

for(int i=0;i<L;i++){

if(temp &(1<<i))v=up[v][i];

}

}

else if(dis[v]<dis[u]){

int temp=dis[u]-dis[v];

for(int i=0;i<L;i++){

if(temp &(1<<i))u=up[u][i];

}

}

if(u==v)return u;

for(int i=L-1;i>=0;i--){

if(up[u][i]!=up[v][i]){

u=up[u][i];

v=up[v][i];

}

}

return up[u][0];

}

void chain_init(int n){

fo1(i,n)chain[i]=i;

}

void dfs_chains(int s,int p){

if(bigchild[s]!=-1){

chain[bigchild[s]]=chain[s];

}

for(auto el:graph[s]){

if(el!=p){

dfs_chains(el,s);

}

}

}

void dfs_labels(int s,int p){

tin[s]=++cnt;

tr.update(barr,tin[s],arr[s]);//segment tree or BIT whichever is better

if(bigchild[s]!=-1) dfs_labels(bigchild[s],s);

for(auto el:graph[s]){

if(el!=p && el!=bigchild[s]){

dfs_labels(el,s);

}

}

}

int get_anc(int u,int k){

fo(i,18){

if(k& 1<<i){

u=up[u][i];

}

}

return u;

}

int query_chains(int u,int p){

//gets the sum till the value below the LCA

int val=0;

while(chain[u]!=chain[p]){

amax(val,tr.query(tin[chain[u]],tin[u]));

u=chain[u];

u=up[u][0];

}

amax(val,tr.query(tin[p],tin[u]));

return val;

}

int path_query(int u,int v){

int lc=LCA(u,v);

int val=max(query_chains(u,lc),query_chains(v,lc));

// amax(val,tr.query(tin[lc],tin[lc]));//bit query;

return val;

}

int path_update(int u,int v){

//will need lazyprop for this

return 0;

}