coreBugZJ

此 blog 已弃。

Query on a tree, ACM-DIY Group Contest 2011 Spring 之 5,HDOJ 3804

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< intint > 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< intint > 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, 0sizeof(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 


posted on 2011-03-26 20:32 coreBugZJ 阅读(1068) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理