vigroh_9's blog

A problem about tree
By vigroh_9, 10 years ago, In English

I'm trying to solve a problem !

I have a tree. Plants with N nodes (N <= 100000).

For any node, the node level 1 is the direct child node and child node level K (K> 1) that all child nodes of the node level 1 level (K-1).

Initially, all nodes have the value 0

I have two queries:

1 u k e: all child note lever k of note u should be increased by e.

2 u: note u how much value.

input:

  • The first line contains the number N

  • N-1 line followed by the pair (u, v), v is the node level 1 of u

  • The next line contains the number of queries M (M <= 500000).

  • M line followed by queries.

output:

  • results for each query 2.

Example

input:

6

1 2

1 3

2 4

3 5

3 6

6

2 6

1 1 2 1000

1 2 1 100

1 3 1 -100

2 4

2 5

output:

0

1100

900

Any ideal to solve it?

Thanks in advance.

(sorry if my English bad)

  • Vote: I like it
  • -20
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Don't you have a link to the problem? It is difficult to understand the text...

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I think simple segment tree <+, sum> is enough. Put vertexes in level-order (first vertexes on 1st level, then from 2nd level, etc.). Note, that for every query one, affected vertexes make contiguous interval.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    That's right, but only as long as nodes with the same level are ordered by the pre-order traversal ID, so that the sub-tree of a given level for any node form a contiguous segment.

    A CHALLENGE: At first I had misunderstood the problem statement and thought the "type 2" query was "Sum of all nodes of sub-tree rooted at u". In case that was the "type 2" query, what would the solution be? I can't think of anything, because the nodes order necessary for "type 1" queries is not good for "type 2", that requires ALL descendants of node u. Anyone has something in mind for that "slight" modification?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      You can use heavy-light decomposition. For each chain you need also segment tree <+, sum>. Query 1: Go through every chain from u and lower and add e to right nodes. Query 2: Sum of all nodes' values in chains which parent u is and <position u, last> in u's chain. Every query in O(log2n)

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I'd like to add that since we're dealing with range updates / point queries, a BIT would be the ideal data structure (it's easier to code and it performs faster).

    My rule of thumb for this is...

    • Range updates / Range queries: Segment Tree
    • Range updates / Point queries: BIT
    • Point updates / Range queries: BIT
    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used a binary search to find the affected interval, and then a BIT to update/query, so the whole complexity is O(Mlog2(n)), and of course it's too slow. Is there anyway to do this in O(Mlogn) ?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      How do you used a binary search to find affected interval ? thank you :D (sorry for my bad english)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Since I cannot explain because of my poor English, I think I should show you my code:

        int getMinID(int i, int k) {
	int l = 0, r = V[H[i] + k].size() - 1, ans = -1;
	while (l <= r) {
		int m = (l + r) >> 1;
		int t = kthParent(V[H[i] + k][m], k);
		if (t >= i) {
			if (t == i) ans = m;
			r = m - 1;
		}
		else l = m + 1;
	}
	return V[H[i] + k][ans];
}
        • V[i] is a vector which contains all vertex on level i
        • H[i] is level of vertex i
        • kthParent() is a function used to get the k-th parent of vertex i
        • This function is used to get the min id of all child level k of vertex i.
        • Now write a similar function to get the max id.
        • All that's left is to update the interval [minID; maxID] using Fenwick Tree / Segment Tree. P/s: you don't actually need V[], you just need 2 value L[i], R[i] which means the left most / right most vertex on level i.
        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why is O(Mlog2(n)) too slow? M = 500000 and N = 100000, so that would be around 150M operations. What's the time limit?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        150M operations could be TLE on Cube cluster with time limit 2s. So I don't think it can run well in 5s on Pyramid :P

        Btw, is there any solution in O(MlogN) ?

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          Whatever the time limit, searching for the interval with binary search and then querying the Segment Tree for the value of that interval is NOT O(Mlog2(n)), since you're not doing a logarithmic query within the binary search, but rather just two successive logarithmic operations (binary search, then tree query). This makes the algorithm O(Mlog(n)).

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh sorry, I forgot to say that my kthParent() function is O(logn) :P Is there anyway to reduce this to O(1) ?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
              ← Rev. 7   Vote: I like it 0 Vote: I do not like it

              Ooohhh, I see...

              Yes, there's a way. What does your kthParent() function do? What I'd do for this problem is have a pair < int, int >  array where the first value is the depth of the nodes and the second value is the pre-order ID. Then, suppose we need to update node u at depth k, and that node's subtree goes from ID a to ID b. What we need to do is lower – bound(k, a) and upper – bound(k, b) on that array to find the interval to update. You need to subtract 1 from upper – bound(k, b) as it turns out.

              → Reply