• <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上的題解,好復(fù)雜,表示沒(méi)看懂

            這個(gè)解法好簡(jiǎn)單,謝謝 Topsky 的指點(diǎn),表示 YM

            手寫棧 DFS 樹中的每個(gè)點(diǎn),用 map 記錄當(dāng)前訪問(wèn)的點(diǎn)到根節(jié)點(diǎn)的所有權(quán)值,用 map 的 upper_bound 求得當(dāng)前訪問(wèn)點(diǎn)上的所有詢問(wèn)的結(jié)果,DFS 結(jié)束后一起輸出結(jié)果。


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

            7777久久亚洲中文字幕| 久久久精品国产亚洲成人满18免费网站 | 久久夜色精品国产噜噜噜亚洲AV| 国产高潮国产高潮久久久| 国产AⅤ精品一区二区三区久久| 久久久噜噜噜久久中文字幕色伊伊| 97精品依人久久久大香线蕉97| 麻豆精品久久精品色综合| 久久久久高潮综合影院| 国产成人久久久精品二区三区| 人妻精品久久久久中文字幕一冢本| 99久久无码一区人妻| 精品国产乱码久久久久久呢| 久久精品99无色码中文字幕| 狠色狠色狠狠色综合久久 | 久久综合视频网| 国产精品日韩深夜福利久久| 久久精品无码专区免费青青| 精品综合久久久久久97| 天天综合久久一二三区| 久久久久亚洲爆乳少妇无| 99精品久久久久久久婷婷| 国产精品视频久久久| 狠狠色丁香久久婷婷综| 久久精品国产亚洲AV电影| 无码日韩人妻精品久久蜜桃| 欧美日韩久久中文字幕| 中文成人久久久久影院免费观看| 久久精品国产99国产精品| 久久精品国产黑森林| 少妇被又大又粗又爽毛片久久黑人| 国产午夜电影久久| 国产精品99久久久久久www| 亚洲狠狠久久综合一区77777| 日本免费一区二区久久人人澡 | 久久亚洲精品无码aⅴ大香| 少妇无套内谢久久久久| 97精品依人久久久大香线蕉97| 婷婷久久香蕉五月综合加勒比| 无码AV中文字幕久久专区| 国产精品一区二区久久 |