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

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
              1#include <cstdio>
              2
              3const int SIZE = 100001;
              4const int INF = 10000000;
              5
              6int N, arr_sc[SIZE], arr_order[SIZE], arr_index[SIZE], edge[SIZE][2], father[SIZE];
              7
              8struct NODE
              9{
             10    int m_v;
             11    struct NODE* next;
             12}            tree[SIZE], mem[SIZE * 2];
             13
             14int index = 0, M = 0, tId = 1;
             15int gMax, gMin;
             16
             17struct ITEM
             18{
             19    int fst;
             20    int last;
             21}            arr_pos[SIZE];
             22
             23struct STREE
             24{
             25    int m_start;
             26    int m_end;
             27
             28    int m_max;
             29    int m_min;
             30    int m_markMin;
             31    int m_markMax;
             32
             33    int m_leftChild;
             34    int m_rightChild;
             35}            stree[SIZE * 2];
             36
             37void Insert(const int& x, const int& y)
             38{
             39    mem[index].m_v = y;
             40    mem[index].next = tree[x].next;
             41    tree[x].next = &mem[index];
             42    index++;
             43
             44    mem[index].m_v = x;
             45    mem[index].next = tree[y].next;
             46    tree[y].next = &mem[index];
             47    index++;
             48}
             49
             50void DFS( const int &root, const int& fat )
             51{
             52    NODE *ptr = tree[root].next;
             53    
             54    arr_pos[root].fst = M;
             55    arr_index[root] = M;
             56    arr_order[M++] = root;
             57    father[root] = fat;
             58
             59    while ( ptr )
             60    {
             61        if ( ptr->m_v != fat )
             62        {
             63            DFS( ptr->m_v, root );
             64        }
             65        ptr = ptr->next;
             66    }
             67
             68    arr_pos[root].last = M - 1;
             69}
             70
             71void Build(const int& id, const int& s, const int& e)
             72{
             73    stree[id].m_start = s;
             74    stree[id].m_end = e;
             75    stree[id].m_max = 0;
             76    stree[id].m_min = INF;
             77    stree[id].m_markMax = -1;
             78    stree[id].m_markMin = -1;
             79    if ( s == e )
             80    {
             81        return;
             82    }
             83
             84    int mid = (s + e) >> 1;
             85
             86    stree[id].m_leftChild = tId++;
             87    Build( stree[id].m_leftChild, s, mid );
             88
             89    stree[id].m_rightChild = tId++;
             90    Build( stree[id].m_rightChild, mid + 1, e );
             91}
             92
             93void InsertTree(const int& id, const int& p, const int& v)
             94{
             95    if ( stree[id].m_max < v )
             96    {
             97        stree[id].m_max = v;
             98        stree[id].m_markMax = arr_order[p];
             99    }
            100    if ( stree[id].m_min > v )
            101    {
            102        stree[id].m_min = v;
            103        stree[id].m_markMin = arr_order[p];
            104    }
            105
            106    if ( stree[id].m_start == p && stree[id].m_end == p )
            107    {
            108        return;
            109    }
            110
            111    int mid = (stree[id].m_start + stree[id].m_end) >> 1;
            112
            113    if ( mid >= p )
            114        InsertTree( stree[id].m_leftChild, p, v );
            115    else
            116        InsertTree( stree[id].m_rightChild, p, v );
            117}
            118
            119void Change( const int& id, const int& p, const int& v )
            120{
            121    if ( stree[id].m_markMax == arr_order[p] )
            122    {
            123        stree[id].m_max = 0;
            124        stree[id].m_markMax = -1;
            125    }
            126    if ( stree[id].m_markMin == arr_order[p] )
            127    {
            128        stree[id].m_min = INF;
            129        stree[id].m_markMin = -1;
            130    }
            131
            132    if ( stree[id].m_leftChild == p && stree[id].m_rightChild == p )
            133    {
            134        stree[id].m_max = stree[id].m_min = v;
            135        stree[id].m_markMax = stree[id].m_markMin = arr_order[p];
            136        return;
            137    }
            138
            139    int mid = (stree[id].m_start + stree[id].m_end) >> 1;
            140
            141    if ( mid >= p )
            142    {
            143        Change( stree[id].m_leftChild, p, v );
            144    }
            145    else {
            146        Change( stree[id].m_rightChild, p, v );
            147    }
            148
            149    int tf = stree[id].m_leftChild, tr = stree[id].m_rightChild, tmark, ts;
            150    
            151    ts = (stree[tf].m_max > stree[tr].m_max ? stree[tf].m_max : stree[tr].m_max);
            152    tmark = (stree[tf].m_max > stree[tr].m_max ? stree[tf].m_markMax : stree[tr].m_markMax );
            153    if ( stree[id].m_max < ts )
            154    {
            155        stree[id].m_max = ts;
            156        stree[id].m_markMax = tmark;
            157    }
            158
            159    ts = (stree[tf].m_min < stree[tr].m_min ? stree[tf].m_min : stree[tr].m_min);
            160    tmark = (stree[tf].m_min < stree[tr].m_min ? stree[tf].m_markMin : stree[tr].m_markMin );
            161    if ( stree[id].m_min > ts )
            162    {
            163        stree[id].m_min = ts;
            164        stree[id].m_markMin = tmark;
            165    }
            166
            167}
            168
            169void Query(const int& id, const int& s, const int& e)
            170{
            171    if ( s == stree[id].m_start && e == stree[id].m_end )
            172    {
            173        if ( gMax < stree[id].m_max )
            174            gMax = stree[id].m_max;
            175        if ( gMin > stree[id].m_min )
            176            gMin = stree[id].m_min;
            177
            178        return;
            179    }
            180
            181    int mid = (stree[id].m_start + stree[id].m_end) >> 1;
            182
            183    if ( mid >= e )
            184    {
            185        Query( stree[id].m_leftChild, s, e );
            186    }
            187    else if ( mid < s )
            188    {
            189        Query( stree[id].m_rightChild, s, e );
            190    }
            191    else {
            192        Query( stree[id].m_leftChild, s, mid );
            193        Query( stree[id].m_rightChild, mid + 1, e );
            194    }
            195}
            196
            197void Solve(const int& ep)
            198{
            199    gMax = 0;
            200    gMin = INF;
            201
            202    __int64 ans;
            203    int x, y, s, e;
            204
            205    x = edge[ep][0], y = edge[ep][1];
            206
            207    if ( y == father[x] )
            208        y = x;
            209
            210    s = arr_pos[y].fst;
            211    e = arr_pos[y].last;
            212
            213    if ( s == e )
            214    {
            215        gMax = gMin = arr_sc[y];
            216    }
            217    else {
            218        Query( 0, s, e );
            219    }
            220
            221    ans = gMax * gMin;
            222
            223    gMax = 0;
            224    gMin = INF;
            225
            226    if ( s > 0 )
            227        Query( 0, 0, s - 1 );
            228
            229    if ( e + 1 <= M - 1 )
            230        Query( 0, e + 1, M - 1 );
            231
            232    ans += gMax * gMin;
            233
            234    printf("%I64d\n", ans);
            235
            236}
            237
            238void Init()
            239{
            240    int i;
            241
            242    for ( i = 0; i < SIZE; ++i )
            243        tree[i].next = NULL;
            244
            245    index = 0;
            246    tId = 1;
            247    M = 0;
            248}
            249
            250int main()
            251 {
            252     freopen("1.txt", "r", stdin);
            253
            254     int cs;
            255     int i, x, y, Q;
            256     char cmd[10];
            257
            258     scanf("%d", &cs);
            259
            260     while ( cs-- )
            261     {
            262         scanf("%d %d", &N, &Q);
            263
            264         for ( i = 1; i <= N; ++i )
            265         {
            266             scanf("%d", &arr_sc[i]);
            267         }
            268
            269         Init();
            270         Build( 0, 0, N - 1 );
            271
            272         for ( i = 0; i < N - 1; ++i )
            273         {
            274             scanf("%d %d", &x, &y);
            275
            276             edge[i + 1][0] = x;
            277             edge[i + 1][1] = y;
            278             Insert( x, y );
            279         }
            280
            281         father[1] = -1;
            282         DFS( 1, -1 );
            283
            284         for ( i = 0; i < M; ++i )
            285         {
            286             int t = arr_order[i];
            287             InsertTree( 0, i, arr_sc[t] );
            288         }
            289
            290         for ( i = 0; i < Q; ++i )
            291         {
            292             scanf("%s", cmd);
            293
            294             if ( cmd[0] == 'Q' )
            295             {
            296                 scanf("%d", &x);
            297            
            298                 Solve( x );
            299             }
            300             else if ( cmd[0] == 'C' )
            301             {
            302                 scanf("%d %d", &x, &y);
            303                 arr_sc[x] = y;
            304                 Change( 0, arr_index[x], y ); 
            305             }
            306         }
            307     }
            308     
            309     return 0;
            310 }
            311
            

	
            
	
	
            
		posted on 2009-05-20 00:13 巫 閱讀(310) 評論(0)  編輯 收藏 引用  所屬分類: 數據結構 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久人妻少妇嫩草AV蜜桃|
国内精品伊人久久久久网站|
日韩十八禁一区二区久久|
亚洲乱亚洲乱淫久久|
久久久黄片|
久久亚洲精品人成综合网|
国产精品亚洲美女久久久|
久久婷婷五月综合国产尤物app
|
久久精品亚洲一区二区三区浴池
|
国内精品久久久人妻中文字幕|
久久久久久久综合日本亚洲|
久久亚洲AV成人无码|
精品久久久久久久无码|
亚洲综合久久久|
segui久久国产精品|
久久精品无码专区免费东京热|
久久99精品久久久久久不卡|
综合网日日天干夜夜久久|
国产成人精品久久亚洲|
久久丫精品国产亚洲av不卡|
久久久久黑人强伦姧人妻|
久久99国产精品久久久|
亚洲中文字幕无码久久2017|
亚洲精品久久久www|
国产精品成人久久久久久久|
久久国产精品久久国产精品|
亚洲国产精品无码成人片久久|
亚洲国产日韩欧美综合久久|
久久狠狠一本精品综合网|
大伊人青草狠狠久久|
91久久婷婷国产综合精品青草|
波多野结衣AV无码久久一区|
久久久久久久免费视频|
亚洲国产高清精品线久久|
久久久久久久综合综合狠狠|
久久久久国产精品麻豆AR影院
|
国产激情久久久久影院小草|
天天久久狠狠色综合|
久久www免费人成看国产片|
99国内精品久久久久久久|
日本亚洲色大成网站WWW久久|