• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(1095) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            久久伊人五月天论坛| 中文字幕无码精品亚洲资源网久久 | 日本欧美国产精品第一页久久| 国产伊人久久| 性欧美大战久久久久久久久| 久久国产精品77777| 久久综合成人网| 国产精品一区二区久久精品| 国产一区二区精品久久岳| 香蕉久久av一区二区三区| 国产成人无码精品久久久免费 | 亚洲精品蜜桃久久久久久| 精品久久久久久亚洲精品| 一级做a爰片久久毛片免费陪| 97r久久精品国产99国产精| 久久99国产精品久久99小说 | 精品综合久久久久久97超人 | 久久久久亚洲AV无码专区首JN| 97久久精品无码一区二区| 国产精品乱码久久久久久软件| 香港aa三级久久三级| 久久精品国产亚洲av影院| 免费精品久久天干天干| 久久夜色精品国产www| 香港aa三级久久三级| 97精品国产91久久久久久| 久久精品国产亚洲77777| 四虎国产精品成人免费久久| 久久免费香蕉视频| 久久精品国产只有精品66| 国产综合成人久久大片91| 久久综合综合久久狠狠狠97色88| 精品人妻久久久久久888| 97精品久久天干天天天按摩| 国产色综合久久无码有码| 亚洲国产另类久久久精品小说| 欧美日韩精品久久免费| 久久无码高潮喷水| 亚洲国产另类久久久精品黑人| 久久久久久国产精品美女| 成人午夜精品无码区久久|