Succinct representations of weighted trees supporting path queries

N. Alon, B. Schieber, Optimal preprocessing for answering on-line product queries, Tech. Rep., Tel Aviv University, 1987. Benoit, 2005, Representing trees of higher degree, Algorithmica, 43, 275, 10.1007/s00453-004-1146-6 Chazelle, 1987, Computing on a free tree via complexity-preserving mappings, Algorithmica, 2, 337, 10.1007/BF01840366 D.R. Clark, J.I. Munro, Efficient suffix trees on secondary storage (extended abstract), in: ACM–SIAM Symposium on Discrete Algorithms, 1996, pp. 383–391. Cole, 2000, An O(nlogn) algorithm for the maximum agreement subtree problem for binary trees, SIAM J. Comput., 30, 1385, 10.1137/S0097539796313477 T. Gagie, S.J. Puglisi, A. Turpin, Range quantile queries: another virtue of wavelet trees, in: International Conference on String Processing and Information Retrieval, 2009, pp. 1–6. R. Grossi, A. Gupta, J.S. Vitter, High-order entropy-compressed text indexes, in: ACM–SIAM Symposium on Discrete Algorithms, 2003, pp. 841–850. Hagerup, 2000, Parallel preprocessing for path queries without concurrent reading, Inform. and Comput., 158, 18, 10.1006/inco.1999.2814 Harel, 1984, Fast algorithms for finding nearest common ancestors, SIAM J. Comput., 13, 338, 10.1137/0213024 M. He, J.I. Munro, G. Zhou, Path queries in weighted trees, in: International Symposium on Algorithms and Computation, 2011, pp. 140–149. M. He, J.I. Munro, G. Zhou, Succinct data structures for path queries, in: European Symposium on Algorithms, 2012. W.-K. Hon, R. Shah, J.S. Vitter, Ordered pattern matching: towards full-text retrieval, Purdue University Tech. Rept. CSD TR 06-008, 2006. G. Jacobson, Space-efficient static trees and graphs, in: IEEE Symposium on Foundations of Computer Science, 1984, pp. 549–554. J. Jansson, K. Sadakane, W.-K. Sung, Ultra-succinct representation of ordered trees, in: ACM–SIAM Symposium on Discrete Algorithms, 2007, pp. 575–584. Krizanc, 2005, Range mode and range median queries on lists and trees, Nordic J. Comput., 12, 1 Lu, 2008, Balanced parentheses strike back, ACM Trans. Algorithms, 4, 10.1145/1367064.1367068 V. Mäkinen, G. Navarro, Position-restricted substring searching, in: Latin American Symposium on Theoretical Informatics, 2006, pp. 703–714. Munro, 2001, Succinct representation of balanced parentheses and static trees, SIAM J. Comput., 31, 762, 10.1137/S0097539799364092