• <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

            国产午夜精品久久久久免费视 | 国内精品伊人久久久久AV影院| 一本色道久久HEZYO无码| 久久99热这里只有精品66| 久久精品国产日本波多野结衣| 蜜臀av性久久久久蜜臀aⅴ麻豆| 久久96国产精品久久久| 亚洲国产精品成人AV无码久久综合影院| 久久午夜福利无码1000合集| 久久久久亚洲精品天堂| 女人高潮久久久叫人喷水| 国产午夜久久影院| 午夜精品久久久久9999高清| 久久综合九色综合97_久久久| 久久综合久久美利坚合众国| 精品久久久久中文字幕日本| 深夜久久AAAAA级毛片免费看| 久久亚洲私人国产精品vA| 久久精品亚洲乱码伦伦中文| 久久er99热精品一区二区| 四虎影视久久久免费| 精品九九久久国内精品| 亚洲综合伊人久久大杳蕉| 日韩欧美亚洲综合久久影院Ds| 69久久夜色精品国产69| 99麻豆久久久国产精品免费 | 伊人丁香狠狠色综合久久| 欧美熟妇另类久久久久久不卡| 久久99精品国产麻豆婷婷| 91精品国产91久久| 国产三级久久久精品麻豆三级| 狠狠综合久久综合88亚洲| 亚洲人AV永久一区二区三区久久 | 婷婷久久精品国产| 久久精品国产99国产精偷| 少妇人妻88久久中文字幕| 九九精品久久久久久噜噜| 久久综合九色综合久99| 色播久久人人爽人人爽人人片aV | 亚洲人AV永久一区二区三区久久| 久久黄色视频|