Query on a tree
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
There are some queries on a tree which has n nodes. Every query is described as two integers (X, Y).For each query, you should find the maximum weight of the edges in set E, which satisfies the following two conditions.
1) The edge must on the path from node X to node 1.
2) The edge’s weight should be lower or equal to Y.
Now give you the tree and queries. Can you find out the answer for each query?
Input
The first line of the input is an integer T, indicating the number of test cases. For each case, the first line contains an integer n indicates the number of nodes in the tree. Then n-1 lines follows, each line contains three integers X, Y, W indicate an edge between node X and node Y whose value is W. Then one line has one integer Q indicates the number of queries. In the next Q lines, each line contains two integers X and Y as said above.
Output
For each test case, you should output Q lines. If no edge satisfy the conditions described above，just output “-1” for this query. Otherwise output the answer for this query.
Sample Input
1
3
1 2 7
2 3 5
4
3 10
3 7
3 6
3 4
Sample Output
7
7
5
-1
Hint
2<=n<=10^5
2<=Q<=10^5
1<=W,Y<=10^9
The data is guaranteed that your program will overflow if you use recursion.
Source
ACM-DIY Group Contest 2011 Spring
OJ上的題解，好復雜，表示沒看懂
這個解法好簡單，謝謝 Topsky 的指點，表示 YM
手寫棧 DFS 樹中的每個點，用 map 記錄當前訪問的點到根節點的所有權值，用 map 的 upper_bound 求得當前訪問點上的所有詢問的結果，DFS 結束后一起輸出結果。
1 #include <iostream>
2 #include <cstdio>
3 #include <map>
4 #include <list>
5 #include <stack>
6 #include <cstring>
7 #include <algorithm>
8
9 using namespace std;
10
11 const int N = 100009;
12 const int Q = 100009;
13
14 typedef pair< int, int > PII;
15 typedef list< PII > LPII;
16 typedef LPII::iterator LPII_I;
17 typedef pair< int, LPII_I > SD;
18 typedef stack< SD > STACK;
19 typedef map< int, int > MII;
20 typedef MII::iterator MII_I;
21
22 int q;
23 LPII qry[ N ]; // y, id
24 int ans[ Q ];
25
26 int n, wf[ N ];
27 LPII adj[ N ]; // node, weight
28
29 void input() {
30 int i, u, v, w;
31 scanf( "%d", &n );
32 for ( i = 1; i <= n; ++i ) {
33 adj[ i ].clear();
34 qry[ i ].clear();
35 }
36 for ( i = 1; i < n; ++i ) {
37 scanf( "%d%d%d", &u, &v, &w );
38 adj[ u ].push_back( PII(v,w) );
39 adj[ v ].push_back( PII(u,w) );
40 }
41 scanf( "%d", &q );
42 for ( i = 1; i <= q; ++i ) {
43 scanf( "%d%d", &u, &v );
44 qry[ u ].push_back( PII(v,i) );
45 }
46 }
47
48 void solve() {
49 static int ink[ N ];
50 SD sd;
51 STACK stk;
52 MII con;
53 LPII_I ite;
54
55 sd.first = 1;
56 sd.second = adj[ 1 ].begin();
57 stk.push( sd );
58 memset( ink, 0, sizeof(ink) );
59 ink[ 1 ] = 1;
60 con[ -1 ] = 1;
61 wf[ 1 ] = -1;
62 for ( ite = qry[ 1 ].begin(); ite != qry[ 1 ].end(); ++ite ) {
63 ans[ ite->second ] = -1;
64 }
65 while ( ! stk.empty() ) {
66 sd = stk.top();
67 stk.pop();
68 if ( sd.second == adj[ sd.first ].end() ) {
69 if ( --con[ wf[ sd.first ] ] < 1 ) {
70 con.erase( wf[ sd.first ] );
71 }
72 }
73 else {
74 int j = sd.second->first;
75 int w = sd.second->second;
76 if ( ink[ j ] ) {
77 ++(sd.second);
78 stk.push( sd );
79 }
80 else {
81 ink[ j ] = 1;
82 wf[ j ] = w;
83 ++(con[ w ]);
84 for ( ite = qry[ j ].begin(); ite != qry[ j ].end(); ++ite ) {
85 MII_I mit = con.upper_bound( ite->first );
86 --mit;
87 ans[ ite->second ] = mit->first;
88 }
89 ++(sd.second);
90 stk.push( sd );
91 sd.first = j;
92 sd.second = adj[ j ].begin();
93 stk.push( sd );
94 }
95 }
96 }
97 }
98
99 void output() {
100 for ( int i = 1; i <= q; ++i ) {
101 printf( "%d\n", ans[ i ] );
102 }
103 }
104
105 int main() {
106 int td, i, u, v, w;
107 scanf( "%d", &td );
108 while ( td-- > 0 ) {
109 input();
110 solve();
111 output();
112 }
113 return 0;
114 }
115