• <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)  編輯 收藏 引用  所屬分類: 數據結構 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



国产午夜精品久久久久九九|
一本一本久久aa综合精品|
久久久久久久99精品免费观看|
狠狠色噜噜狠狠狠狠狠色综合久久|
91久久福利国产成人精品|
久久久久青草线蕉综合超碰|
97久久精品无码一区二区
|
国产成人精品久久免费动漫|
国产精品无码久久综合网|
九九精品久久久久久噜噜|
国产欧美久久一区二区|
久久久午夜精品|
国产午夜精品久久久久九九|
久久伊人精品一区二区三区|
国产成人精品久久综合|
国产精品久久永久免费|
久久精品中文騷妇女内射|
一级做a爰片久久毛片毛片|
狠狠人妻久久久久久综合|
久久久久亚洲AV片无码下载蜜桃|
色综合久久夜色精品国产|
国产精品久久久99|
精品综合久久久久久97超人
|
国产综合成人久久大片91|
久久久久亚洲av无码专区喷水|
免费无码国产欧美久久18|
亚洲国产香蕉人人爽成AV片久久|
精品久久久久一区二区三区|
蜜桃麻豆www久久|
伊人久久大香线蕉影院95|
热久久这里只有精品|
青青草国产精品久久|
国产精品成人精品久久久|
99精品伊人久久久大香线蕉|
欧美一区二区精品久久|
国产美女久久精品香蕉69|
亚洲国产精品无码久久一线|
久久婷婷五月综合97色一本一本|
午夜精品久久久久久毛片|
久久99国产综合精品女同|
2021精品国产综合久久|