Kyooma's Blog

题目合集

  • ~41.27K 字
  1. 1. 模拟
    1. 1.0.1. jiubei and regexp
    2. 1.0.2. jiubei and website
    3. 1.0.3. jiubei and vscode
    4. 1.0.4. All in
    5. 1.0.5. Jiubei And Hearthstone Battlegrounds
    6. 1.0.6. jiubei and pstree
    7. 1.0.7. jiubei and TFT
    8. 1.0.8. jiubei and sgs
  • 2. 树上问题
    1. 2.0.1. CCPC高职场L
    2. 2.0.2. Monkey Joe

    • 模拟

    jiubei and regexp

    CODE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    #include <stdio.h>
    #include <string.h>
    int a[3000][62];//0-25 a-z   26-51 A-Z  52-61 0-9
    char k[3009];
    int jud(int i,int n);
    int main(){
    	int n=1,len,m,q,m1;
    	scanf("%s",k);
    	len=strlen(k);
    	for(int i=0;i<len;i++){
    		if(k[i]=='[') continue;
    		if(k[i]==']'){
    			n++;
    			continue;
    		}
    		if(k[i]>='a' && k[i]<='z'){
    			m=k[i]-'a';
    			a[n][m]=1;
    		}else if(k[i]>='A' && k[i]<='Z'){
    			m=k[i]-'A'+26;
    			a[n][m]=1;
    		}else if(k[i]>='0' && k[i]<='9'){
    			m=k[i]-'0'+52;
    			a[n][m]=1;
    		}else if(k[i]=='-'){
    			if(k[i+1]>='a' && k[i+1]<='z'){
    				m1=k[i+1]-'a';
    			}else if(k[i+1]>='A' && k[i+1]<='Z'){
    				m1=k[i+1]-'A'+26;
    			}else if(k[i+1]>='0' && k[i+1]<='9'){
    				m1=k[i+1]-'0'+52;
    			}
    			if(m>m1){
    				for(int j=m1;j<=m;j++){
    					a[n][j]=1;
    				}
    			}else{
    				for(int j=m;j<=m1;j++){
    					a[n][j]=1;
    				}
    			}
    		}
    	}
    	n--;
    	scanf("%d\n",&q);
    	for(int i=0;i<q;i++){
    		int f=1;
    		scanf("%s",k);
    		len=strlen(k);
    		for(int j=0;j<len-n+1;j++){
    			if(jud(j,n)){
    				printf("%d\n",j);
    				f=0;
    				break;
    			}
    		}
    		if(f) printf("-1\n");
    	}
    } 
    int jud(int i,int n){
    	int m;
    	for(int j=1;j<=n;j++){
    		if(k[i]>='a' && k[i]<='z'){
    			m=k[i]-'a';
    		}else if(k[i]>='A' && k[i]<='Z'){
    			m=k[i]-'A'+26;
    		}else if(k[i]>='0' && k[i]<='9'){
    			m=k[i]-'0'+52;
    		}
    		if(a[j][m]){
    			i++;
    		}else{
    			return 0;
    		}
    	}
    	return 1;
    }

    jiubei and website

    CODE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #include <stdio.h>
    #include <string.h>
    char k[100000];
    int main(){
        scanf("%s",k);
        int len=strlen(k),i=0;
        while(i<len){
            if(k[i]=='?' || k[i]=='&'){
                i++;
                while(k[i]!='?' && k[i]!='&' && i<len){
                    if(k[i]=='='){
                        putchar(' ');
                    }else{
                        putchar(k[i]);
                    }
                    i++;
                }
                putchar('\n');
            }else{
                i++;
            }
        }
    }

    jiubei and vscode

    CODE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    #include <stdio.h>
    #include <string.h>
    char k[1000000];
    int wz[100000];
    void rua(int cnt);//补空格专用 
    void sw(char m);
    int f=0;
    int main(){
    	scanf("%s",k);
    	int len=strlen(k),i=0,cnt=0,n=0;//n为>位置，cnt为空格数量 
    	putchar('<');
    	while(i<len){
    		if(k[i]!='>'){
    			sw(k[i]);
    		}else{
    			wz[n++]=i;
    			if(f){
    				putchar('"');
    				f=0;
    			}
    			putchar('>');
    			putchar('\n');
    			cnt+=2;
    			rua(cnt);
    			putchar('<');
    		}
    		i++;
    	}
    	if(f) putchar('"');
    	putchar('>');
    	putchar('\n');
    	while(cnt>0){
    		rua(cnt);
    		printf("</");
    		i=wz[n-1]+1;
    		while(k[i]!='&' && k[i]!='@' && i<len && k[i]!='>'){
    			putchar(k[i]);
    			i++;
    		}
    		n--;
    		putchar('>');
    		cnt-=2;
    		putchar('\n');
    	}
    	printf("</");
    	int km;
    	if(wz[0]==0) km=len; else km=wz[0];
    	for(i=0;i<km;i++){
    		if(k[i]!='@' && k[i]!='&'){
    			putchar(k[i]);
    		}else{
    			break;
    		}
    	}
    	putchar('>');
    }
    void rua(int cnt){
    	for(int i=0;i<cnt;i++){
    		putchar(' ');
    	}
    }
    void sw(char m){
    	if(m=='&'){
    		if(f){
    			putchar('"');
    			f=0;
    		}
    		putchar(' ');
    	}else if(m=='='){
    		f=1;
    		putchar(m);
    		putchar('"');
    	}else if(m=='@'){
    		f=1;
    		printf(" id=");
    		putchar('"');
    	}else{
    		putchar(m);
    	}
    }

    All in

    CODE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    #include <bits/stdc++.h>
    using namespace std;
     
    string card[5];
    int hile[5], bbg[5];
    unordered_map<char,int> mp;
    int rank_jud(int a[]){
        int flag = 1;
        for(int i=0;i<5;i++){
            if(card[i][0]!=card[0][0]){
                flag = 0;
            }
            a[i] = mp[card[i][1]];
        }
        sort(a,a+5);
        int tf = 1;
        for(int i=1;i<5;i++){
            if(a[i]!=a[i-1]+1) tf=0;
        }
        if(a[0]==2 && a[1]==3 && a[2]==4 && a[3]==5 && a[4]==14){
            tf=1;
            for(int i = 3; i >= 0; i--) a[i+1] = a[i];
            a[0] = 1;
        }
        if(tf){
            if(flag) return 1;//同花顺
            return 5;//顺子
        }
     
        if((a[0]==a[1] && a[1]==a[2] && a[2]==a[3]) || (a[4]==a[1] && a[1]==a[2] && a[2]==a[3])) return 2;//四条
     
        if((a[0]==a[1] && a[1]==a[2] && a[3]==a[4]) || (a[3]==a[1] && a[1]==a[2] && a[0]==a[4]) || (a[2]==a[3] && a[3]==a[4] && a[0]==a[1])) return 3;//葫芦
     
        if(flag) return 4;//同花
     
        if((a[0]==a[1] && a[1]==a[2]) || (a[3]==a[1] && a[1]==a[2]) || (a[2]==a[3] && a[3]==a[4])) return 6;//三条
     
        if((a[0]==a[1] && a[2]==a[3]) || (a[0]==a[1] && a[4]==a[3]) || (a[2]==a[1] && a[3]==a[4])) return 7;//两对
     
        for(int i=1;i<5;i++){
            if(a[i]==a[i-1]){
                return 8;//一对
            }
        }
     
        return 9;//高牌
    }
     
    int jud_same(int r){
        if(r==1 || r==5) return hile[0]>bbg[0];
        if(r==2){
            int h,b;
            if(hile[0]==hile[1]) h = hile[4]; else h = hile[0];
            if(bbg[0]==bbg[1]) b = bbg[4]; else b = bbg[0];
            return h>b;
        }
        if(r==3){
            int h1,b1,h2,b2;
            for(int i=0;i+2<5;i++){
                if(hile[i]==hile[i+1] && hile[i]==hile[i+2]){
                    h1=hile[i];
                    if(i) h2=hile[i-1]; else h2=hile[4];
                    break;
                }
            }
            for(int i=0;i+2<5;i++){
                if(bbg[i]==bbg[i+1] && bbg[i]==bbg[i+2]){
                    b1=bbg[i];
                    if(i) b2=bbg[i-1]; else b2=bbg[4];
                    break;
                }
            }
            if(h1!=b1) return h1>b1;
            return h2>b2;
        }
        if(r==4){
            for(int i=4;i>=0;i--){
                if(hile[i]!=bbg[i]) return hile[i]>bbg[i];
            }
        }
        if(r==6){
            int h1,b1,h2,b2,h3,b3;
            for(int i=0;i+2<5;i++){
                if(hile[i]==hile[i+1] && hile[i]==hile[i+2]){
                    h1=hile[i];
                    if(i==2) h2=hile[1]; else h2=hile[4];
                    if(!i) h3=hile[3]; else h3=hile[0];
                    break;
                }
            }
            for(int i=0;i+2<5;i++){
                if(bbg[i]==bbg[i+1] && bbg[i]==bbg[i+2]){
                    b1=bbg[i];
                    if(i==2) b2=bbg[1]; else b2=bbg[4];
                    if(!i) b3=bbg[3]; else b3=bbg[0];
                    break;
                }
            }
            if(h1!=b1) return h1>b1;
            if(h2!=b2) return h2>b2;
            return h3>b3;
        }
        if(r==7){
            int h1,b1,h2,b2,h3,b3;
            if(hile[0]==hile[1] && hile[2]==hile[3]){
                h1=hile[2];
                h2=hile[1];
                h3=hile[4];
            }else if(hile[0]==hile[1] && hile[4]==hile[3]){
                h1=hile[3];
                h2=hile[1];
                h3=hile[2];
            }else{
                h1=hile[3];
                h2=hile[1];
                h3=hile[0];
            }
            if(bbg[0]==bbg[1] && bbg[2]==bbg[3]){
                b1=bbg[2];
                b2=bbg[1];
                b3=bbg[4];
            }else if(bbg[0]==bbg[1] && bbg[4]==bbg[3]){
                b1=bbg[3];
                b2=bbg[1];
                b3=bbg[2];
            }else{
                b1=bbg[3];
                b2=bbg[1];
                b3=bbg[0];
            }
            if(h1!=b1) return h1>b1;
            if(h2!=b2) return h2>b2;
            return h3>b3;
        }
        if(r==8){
            int h,b;
            vector<int> th,tb;
            for(int i=4;i>0;i--){
                if(hile[i]==hile[i-1]){
                    h=hile[i];
                    break;
                }
            }
            for(int i=4;i>0;i--){
                if(bbg[i]==bbg[i-1]){
                    b=bbg[i];
                    break;
                }
            }
            for(int i=4;i>=0;i--){
                if(hile[i]!=h) th.push_back(hile[i]);
                if(bbg[i]!=b) tb.push_back(bbg[i]);
            }
            if(h!=b) return h>b;
            for(int i=0;i<th.size();i++){
                if(th[i]!=tb[i]) return th[i]>tb[i];
            }
        }
        for(int i=4;i>=0;i--){
            if(hile[i]!=bbg[i]) return hile[i]>bbg[i];
        }
        return 0;
    }
     
    void solve(){
        for(int i=0;i<5;i++){
            cin >> card[i];
        }
        int r1 = rank_jud(hile);
        for(int i=0;i<5;i++){
            cin >> card[i];
        }
        int r2 = rank_jud(bbg);
        if(r1<r2){
            cout << "All in!\n";
        }else if(r1>r2){
            cout << "Pass\n";
        }else{
            if(jud_same(r1)) cout << "All in!\n";
            else cout << "Pass\n";
        }
    }
     
    int main(){
        int T;
        for(int i=2;i<=9;i++){
            char k = '0'+i;
            mp[k]=i;
        }
        mp['T']=10;mp['J']=11;mp['Q']=12;mp['K']=13;mp['A']=14;
        ios::sync_with_stdio(0);
        cin >> T;
        while(T--) solve();
    }

    Jiubei And Hearthstone Battlegrounds

    CODE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    //
    // Created by Kyooma on 2021/1/2.
    //
    #include <bits/stdc++.h>
    using namespace std;
    struct ch{
        int hp,atk;
        int a[5];//依次为0嘲讽 1圣盾 2复生 3剧毒 4亡语
        int b[5];//只有当存在复生时启用
        int x,y,z;//只有当存在亡语时启用
    };
    ch p[2][1009];//p0为jiubei gg
    char k[100000];
    int l1=0,l2=0,r1,r2;//左边界和右边界
    void judge(int ii,int kk){
        int len=0;
        do{
            scanf("%c",&k[len++]);
        }while(k[len-1]!='\n');
        len--;
        for(int i=0;i<5;i++) p[kk][ii].a[i]=0;
        if(!len) return;
        for(int i=0;i<len;i++){//技能存储
            if(k[i]=='T'){
                p[kk][ii].a[0]=1;
                i+=3;
            }else if(k[i]=='R'){
                p[kk][ii].a[2]=1;
                i+=4;
            }else if(k[i]=='P'){
                p[kk][ii].a[3]=1;
                i+=7;
            }else if(k[i]=='D'){
                if(k[i+1]=='i'){
                    p[kk][ii].a[1]=1;
                    i+=11;
                }else{
                    p[kk][ii].a[4]=1;
                    int j=i+12,cnt=1,res=0;
                    while(k[j]!=')'){
                        if(k[j]==','){
                            if(cnt==1){
                                p[kk][ii].x=res;
                            }else if(cnt==2){
                                p[kk][ii].y=res;
                            }
                            cnt++;
                            res=0;
                        }else{
                            res=res*10+k[j]-'0';
                        }
                        j++;
                    }
                    p[kk][ii].z=res;
                    i=j-1;
                }
            }
        }
        if(p[kk][ii].a[2]){
            for(int i=0;i<5;i++){
                p[kk][ii].b[i]=p[kk][ii].a[i];
            }
            p[kk][ii].b[2]=0;
        }
    }
    int main(){
        int kk=0;
        scanf("%d%d",&r1,&r2);
        for(int i=0;i<r1;i++){
            scanf("%d/%d",&p[kk][i].atk,&p[kk][i].hp);
            judge(i,kk);
        }
        kk=1;
        for(int i=0;i<r2;i++){
            scanf("%d/%d",&p[kk][i].atk,&p[kk][i].hp);
            judge(i,kk);
        }
        //开始battle
        while(l1<r1 && l2<r2){
            int cf=l2;//jiubei 回合
            for(int i=l2;i<r2;i++){//找嘲讽
                if(p[1][i].a[0]){
                    cf=i;
                    break;
                }
            }
            p[1][cf].hp-=p[0][l1].atk;
            p[0][l1].hp-=p[1][cf].atk;
            if(p[1][cf].a[1]){//有圣盾
                p[1][cf].a[1]=0;
                p[1][cf].hp+=p[0][l1].atk;
            }else if(p[0][l1].a[3]){//有毒
                p[1][cf].hp=0;
            }
            if(p[0][l1].a[1]){//有圣盾
                p[0][l1].a[1]=0;
                p[0][l1].hp+=p[1][cf].atk;
            }else if(p[1][cf].a[3]){//有毒
                p[0][l1].hp=0;
            }
            //判断死亡
            if(p[0][l1].hp<=0){// 0 l1随从
                if(p[0][l1].a[4]){//有亡语
                    for(int j=0;j<p[0][l1].z;j++){
                        for(int jb=0;jb<5;jb++) p[0][r1].a[jb]=0;
                        p[0][r1].hp=p[0][l1].y;
                        p[0][r1].atk=p[0][l1].x;
                        r1++;
                    }
                }
                if(p[0][l1].a[2]){//有复生
                    for(int i=0;i<5;i++) p[0][l1].a[i]=p[0][l1].b[i];//重置技能
                    p[0][l1].hp=1;
                }
                if(p[0][l1].hp<=0) l1++;
            }
            if(p[1][cf].hp<=0){// 1 cf随从
                if(p[1][cf].a[4]){//有亡语
                    for(int j=0;j<p[1][cf].z;j++){
                        for(int jb=0;jb<5;jb++) p[1][r2].a[jb]=0;
                        p[1][r2].hp=p[1][cf].y;
                        p[1][r2].atk=p[1][cf].x;
                        r2++;
                    }
                }
                if(p[1][cf].a[2]){//有复生
                    for(int i=0;i<5;i++) p[1][cf].a[i]=p[1][cf].b[i];//重置技能
                    p[1][cf].hp=1;
                }
                if(p[1][cf].hp<=0){//实质死亡
                    if(cf==l2) {
                        l2++;
                    } else {
                        for(int j=cf;j<r2-1;j++){
                            p[1][j]=p[1][j+1];
                        }
                        r2--;
                    }
                }
            }
            if(l1>=r1 || l2>=r2) break;
            cf=l1;//对手 回合
            for(int i=l1;i<r1;i++){//找嘲讽
                if(p[0][i].a[0]){
                    cf=i;
                    break;
                }
            }
            p[0][cf].hp-=p[1][l2].atk;
            p[1][l2].hp-=p[0][cf].atk;
            if(p[0][cf].a[1]){//有圣盾
                p[0][cf].a[1]=0;
                p[0][cf].hp+=p[1][l2].atk;
            }else if(p[1][l2].a[3]){//有毒
                p[0][cf].hp=0;
            }
            if(p[1][l2].a[1]){//有圣盾
                p[1][l2].a[1]=0;
                p[1][l2].hp+=p[0][cf].atk;
            }else if(p[0][cf].a[3]){//有毒
                p[1][l2].hp=0;
            }
            //判断死亡
            if(p[1][l2].hp<=0){//1 l2随从
                if(p[1][l2].a[4]){//有亡语
                    for(int j=0;j<p[1][l2].z;j++){
                        for(int jb=0;jb<5;jb++) p[1][r2].a[jb]=0;
                        p[1][r2].hp=p[1][l2].y;
                        p[1][r2].atk=p[1][l2].x;
                        r2++;
                    }
                }
                if(p[1][l2].a[2]){//有复生
                    for(int i=0;i<5;i++) p[1][l2].a[i]=p[1][l2].b[i];//重置技能
                    p[1][l2].hp=1;
                }
                if(p[1][l2].hp<=0) l2++;
            }
            if(p[0][cf].hp<=0){
                if(p[0][cf].a[4]){//有亡语
                    for(int j=0;j<p[0][cf].z;j++){
                        for(int jb=0;jb<5;jb++) p[0][r1].a[jb]=0;//技能初始化
                        p[0][r1].hp=p[0][cf].y;
                        p[0][r1].atk=p[0][cf].x;
                        r1++;
                    }
                }
                if(p[0][cf].a[2]){//有复生
                    for(int i=0;i<5;i++) p[0][cf].a[i]=p[0][cf].b[i];//重置技能
                    p[0][cf].hp=1;
                }
                if(p[0][cf].hp<=0){
                    if(cf==l1) {
                        l1++;
                    } else {
                        for(int j=cf;j<r1-1;j++){
                            p[0][j]=p[0][j+1];
                        }
                        r1--;
                    }
                }
            }
        }
        if(l1<r1){//jiubei win
            int cnt=r1-l1;
            printf("%d\n",cnt);
            for(int i=l1;i<r1;i++){
                printf("%d/%d\n",p[0][i].atk,p[0][i].hp);
            }
        }else{
            int cnt=r2-l2;
            printf("%d\n",cnt);
            for(int i=l2;i<r2;i++){
                printf("%d/%d\n",p[1][i].atk,p[1][i].hp);
            }
        }
    }

    jiubei and pstree

    CODE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    #include <bits/stdc++.h>

    using namespace std;
    typedef long long ll;
    const int N = 1e5 + 10;

    vector<int> e[N], r[N];
    string ans[N], id[N];
    int pos[N], tot = 1, d[N], root, f[N], mx[N], row[N];

    void dfs(int u, int fa){
    	sort(e[u].begin(), e[u].end());
        if(!e[u].empty()) mx[u] = e[u].back();
    	r[tot].push_back(u);
        row[u] = tot;
        f[u] = fa;
        for(int i = 0; i < e[u].size(); i++){
            if(!i){
                dfs(e[u][i], u);
            }else{
                tot++;
                dfs(e[u][i], u);
            }
        }
    }

    void solve(){
    	int n;
    	cin >> n;
    	for(int i = 1; i < n; i++){
    		int u, v;
    		cin >> u >> v;
    		e[u].push_back(v);
    		d[v]++;
    	}
    	for(int i = 1; i <= n; i++){
    		cin >> id[i];
    		if(!d[i]) root = i;
    	}
    	dfs(root, 0);
        for(int i = 1; i <= tot; i++){
            for(int j = 0; j < pos[f[r[i][0]]]; j++){
                ans[i] += ' ';
            }
            if(i > 1){
                ans[i] += '|';
                if(r[i][0] == mx[f[r[i][0]]]) ans[i] += '_';
                else ans[i] += '-';
            }
            for(int j = i - 1; j > row[f[r[i][0]]]; j--){
                ans[j][pos[f[r[i][0]]]] = '|';
            }
            ans[i] += id[r[i][0]];
            for(int j = 1; j < r[i].size(); j++){
                ans[i] += "---";
                pos[r[i][j - 1]] = (int)ans[i].size() - 2;
                ans[i] += id[r[i][j]];
            }
        }
    	for(int i = 1; i <= tot; i++){
    		cout << ans[i] << '\n';
    	}
    }

    int main(){
    	int T = 1;
    //	cin >> T;
    	while(T--) solve();
    	return 0;
    }

    jiubei and TFT

    CODE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    #include <stdio.h>
    #include <string.h>
    int change();
    int a[50],b[50];//a[i]为1 / 0 记选否,b[i] 记 i号羁绊的出现次数 
    void find(int kk,int cnt);
    void re(){
    	for(int i=1;i<50;i++) b[i]=0;
    }
    struct jb{
    	int num=0;//指羁绊有几层 
    	int peo[7];//指满足人数 
    	int atk[7];//指满足peo[i]后每人增加的战斗力 
    };
    struct hero{
    	int atk;
    	int num;//羁绊个数 
    	int jbb[20];
    }; 
    int n,m,k;//n为人数,m为羁绊数,k为抓取壮丁数 
    char name[20][50];
    char k1[50];
    jb con[10];//存羁绊
    hero p[50];//存人物信息 
    int max=0; 
    int jud();
    int main(){
    	scanf("%d%d%d",&n,&m,&k);
    	getchar();
    	for(int i=1;i<=m;i++){
    		scanf("%s",name[i]);
    		scanf("%d",&con[i].num);
    		for(int j=1;j<=con[i].num;j++){
    			scanf("%d%d",&con[i].peo[j],&con[i].atk[j]);
    		}
    		getchar();
    	}
    	for(int i=1;i<=n;i++){
    		scanf("%s",k1);
    		scanf("%d",&p[i].atk);
    		scanf("%d",&p[i].num);
    		for(int j=1;j<=p[i].num;j++){
    			scanf("%s",k1);
    			int kk=change();
    			p[i].jbb[j]=kk;
    		}
    		getchar();
    	}
    	find(1,0);
    	printf("%d\n",max);
    } 
    int change(){
    	for(int i=1;i<=m;i++){
    		int f=1;
    		int len1=strlen(name[i]);
    		int len2=strlen(k1);
    		if(len1==len2){
    			for(int j=0;j<len1;j++){
    				if(k1[j]!=name[i][j]){
    					f=0;break;
    				}
    			}
    			if(f) return i;
    		}
    	}
    }
    void find(int kk,int cnt){
    	if(cnt==k){//选了k个 
    		int slz=0;
    		re();
    		for(int j=1;j<=n;j++){
    			if(a[j]){
    				slz+=p[j].atk;
    				for(int z=1;z<=p[j].num;z++){
    					b[p[j].jbb[z]]++;
    				} 
    			}
    		}
    		slz+=jud();
    		if(slz>max) max=slz;
    	}
    	for(int i=kk;i<=n;i++){
    		if(a[i]) continue;
    		a[i]=1;
    		find(i+1,cnt+1);
    		a[i]=0;
    	}
    }
    int jud(){
    	int res=0;
    	for(int i=1;i<=m;i++){
    		if(b[i]){
    			for(int j=con[i].num;j>=1;j--){
    				if(b[i]>=con[i].peo[j]){
    					res+=(b[i]*con[i].atk[j]);
    					break;
    				}
    			}
    		}
    	}
    	return res;
    }

    jiubei and sgs

    CODE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    330
    331
    332
    333
    334
    335
    336
    337
    338
    339
    340
    341
    342
    343
    344
    345
    346
    347
    348
    349
    350
    351
    352
    353
    354
    355
    356
    357
    358
    359
    #include <stdio.h>
    #include <string.h>
    char k[100];
    int p1,p2;//1赵云  2周瑜  3张飞  4廖化 5许褚 6吕布 7貂蝉 
    int a1[200];//玩家1手牌 0桃 1杀 2闪 
    int b1[3];//储存各种手牌数量 
    int a2[200];
    int b2[3];
    int len1=0,len2=0,hp1,hp2,lenn=0,cnum1,cnum2;//手牌数量 血量 lenn为卡堆数 ,cnum*为当前手牌数 
    int card[209];//牌堆
    int judp();//转换编号 
    void take(int n,int f);//拿牌，n为牌数，f取1 2 为玩家 
    void find1(int k);//查找p1玩家的k号牌并打出(置为-1
    void find2(int k);
    int jud(int f);//f为玩家 判断出闪否 1为是 0为否 
    int main(){
        int n,m1=2,m2=2,dmg1=1,dmg2=1;
        p1=judp();//转换为英雄编号并设置初始血量 
        if(p1==2 || p1==7) hp1=3; else hp1=4;
        p2=judp();
        if(p2==2 || p2==7) hp2=3; else hp2=4;
        if(p1==2){//设置摸牌数量 
            m1=3;
        }else if(p1==5){
            m1=1;
            dmg1=2; 
        }
        if(p2==2){
            m2=3;
        }else if(p2==5){
            m2=1;
            dmg2=2;
        }
        for(int i=1;i<=3;i++){//摸起始牌 
            scanf("%d",&n);
            getchar();
            take(n,i);
        }
        int hpn1=hp1,hpn2=hp2,kk=0;//hpn*表示玩家当前血量 ,kk表示牌堆顶 
        cnum1=len1;cnum2=len2; 
        int mmm;//为弃牌数量 
        while(1){
            //玩家1摸牌
            //m为摸牌数 
            if(p1==4){//额外的出牌阶段 
                while(b1[0] && hpn1<hp1){//恰桃 
                    find1(0);
                    hpn1++; 
                } 
                if(b1[1]){//判断p1是否有杀 
                    find1(1);
                    if(!jud(2)){//p2没防住 
                        hpn2-=dmg1;
                        while(hpn2<=0 && b2[0]){
                            hpn2++;
                            find2(0);
                        }
                        if(hpn2<=0){printf("win\n");break;}
                    }
                }
            }//额外出牌阶段结束 
            for(int i=0;i<m1;i++){//摸牌 
                a1[len1++]=card[kk++];
                b1[a1[len1-1]]++;
                cnum1++;
            }
            if(kk>lenn){//判断平局否 
                printf("draw\n");
                break;
            }
            //摸牌结束,开始出牌
            while(b1[0] && hpn1<hp1){//恰桃 
                find1(0);
                hpn1++; 
            } 
     
            if(p1==3){//出杀 
                while(b1[1]){
                    find1(1);
                    if(!jud(2)){
                        hpn2-=dmg1;
                        while(hpn2<=0 && b2[0]){
                            hpn2++;
                            find2(0);
                        }
                        if(hpn2<=0){printf("win\n");goto out;}
                    }
                }
            }else{
                if(b1[1]){//判断p1是否有杀 
                    find1(1);
                    if(!jud(2)){
                        hpn2-=dmg1;
                        while(hpn2<=0 && b2[0]){
                            hpn2++;
                            find2(0);
                        }
                        if(hpn2<=0){printf("win\n");break;}
                    }
                }else{
                    if(p1==1 && b1[2]){
                        find1(2);
                        if(!jud(2)){
                            hpn2-=dmg1;
                            while(hpn2<=0 && b2[0]){
                                hpn2++;
                                find2(0);
                            }
                            if(hpn2<=0){printf("win\n");break;}
                        }
                    }
                }
            }
            //p1出牌阶段结束,开始弃牌阶段
            if(p1==2) mmm=3; else mmm=hpn1; 
            while(cnum1>mmm){
                for(int i=0;i<len1;i++){
                    if(a1[i]!=-1){
                        b1[a1[i]]--;
                        a1[i]=-1;
                        cnum1--;
                        break;
                    }
                }
            }
            if(p1==7){
                a1[len1++]=card[kk++];
                b1[a1[len1-1]]++;
                cnum1++;
                if(kk>lenn){//判断平局否 
                    printf("draw\n");
                    break;
                }
            }
            //p1回合结束 
            //开始p2回合 
            if(p2==4){//额外的出牌阶段 
                while(b2[0] && hpn2<hp2){//恰桃 
                    find2(0);
                    hpn2++; 
                } 
                if(b2[1]){//判断p2是否有杀 
                    find2(1);
                    if(!jud(1)){
                        hpn1-=dmg2;
                        while(hpn1<=0 && b1[0]){
                            hpn1++;
                            find1(0);
                        }
                        if(hpn1<=0){printf("lose\n");break;}
                    }
                }
            }//额外出牌阶段结束 
            for(int i=0;i<m2;i++){//摸牌 
                a2[len2++]=card[kk++];
                b2[a2[len2-1]]++;
                cnum2++;
            }
            if(kk>lenn){//判断平局否 
                printf("draw\n");
                break;
            }
            //摸牌结束,开始出牌
            while(b2[0] && hpn2<hp2){//恰桃 
                find2(0);
                hpn2++; 
            } 
     
            if(p2==3){//出杀 
                while(b2[1]){
                    find2(1);
                    if(!jud(1)){
                        hpn1-=dmg2;
                        while(hpn1<=0 && b1[0]){
                            hpn1++;
                            find1(0);
                        }
                        if(hpn1<=0){printf("lose\n");goto out;}
                    }
                }
            }else{
                if(b2[1]){//判断p2是否有杀 
                    find2(1);
                    if(!jud(1)){
                        hpn1-=dmg2;
                        while(hpn1<=0 && b1[0]){
                            hpn1++;
                            find1(0);
                        }
                        if(hpn1<=0){printf("lose\n");break;}
                    }
                }else{
                    if(p2==1 && b2[2]){
                        find2(2);
                        if(!jud(1)){
                            hpn1-=dmg2;
                            while(hpn1<=0 && b1[0]){
                                hpn1++;
                                find1(0);
                            }
                            if(hpn1<=0){printf("lose\n");break;}
                        }
                    }
                }
            }
            //p2出牌阶段结束,开始弃牌阶段
            if(p2==2) mmm=3; else mmm=hpn2; 
            while(cnum2>mmm){
                for(int i=0;i<len2;i++){
                    if(a2[i]!=-1){
                        b2[a2[i]]--;
                        a2[i]=-1;
                        cnum2--;
                        break;
                    }
                }
            }
            if(p2==7){
                a2[len2++]=card[kk++];
                b2[a2[len2-1]]++;
                cnum2++;
                if(kk>lenn){//判断平局否 
                    printf("draw\n");
                    break;
                }
            }   
        }
        out:
        return 0;   
    } 
    int judp(){
        scanf("%s",k);
        if(k[0]=='z'){
            if(k[3]=='o') return 1;
            if(k[2]=='a') return 3;
            return 2;
        }
        if(k[0]=='l'){
            if(k[1]=='i') return 4;
            return 6;
        }
        if(k[0]=='x') return 5;
        return 7;
    }
    void take(int n,int f){
        if(f==1){
            for(int i=1;i<=n;i++){
                scanf("%s",k);
                if(strlen(k)==4){
                    a1[len1++]=2;
                    b1[2]++;
                }else if(k[0]=='s'){
                    a1[len1++]=1;
                    b1[1]++;
                }else if(k[0]=='t'){
                    a1[len1++]=0;
                    b1[0]++;
                }
            }
        }else if(f==2){
            for(int i=1;i<=n;i++){
                scanf("%s",k);
                if(strlen(k)==4){
                    a2[len2++]=2;
                    b2[2]++;
                }else if(k[0]=='s'){
                    a2[len2++]=1;
                    b2[1]++;
                }else if(k[0]=='t'){
                    a2[len2++]=0;
                    b2[0]++;
                }
            }
        }else{
            for(int i=1;i<=n;i++){
                scanf("%s",k);
                if(strlen(k)==4){
                    card[lenn++]=2;
                }else if(k[0]=='s'){
                    card[lenn++]=1;
                }else if(k[0]=='t'){
                    card[lenn++]=0;
                }
            }
        }
    }
    void find1(int k){
        for(int i=0;i<len1;i++){
            if(a1[i]==k){
                a1[i]=-1;
                b1[k]--;
                cnum1--;
                break;
            }
        }
    }
    void find2(int k){
        for(int i=0;i<len2;i++){
            if(a2[i]==k){
                a2[i]=-1;
                b2[k]--;
                cnum2--;
                break;
            }
        }
    }
    int jud(int f){
        if(f==1){//玩家2对玩家1出杀 
            if(b1[2]){
                find1(2);
                if(p2==6){//对方吕布 
                    if(b1[2]){
                        find1(2);return 1;
                    }else{//没闪 
                        if(p1==1 && b1[1]){find1(1);return 1;}
                        return 0;   
                    }
                }else{
                    return 1;
                }
            }else{//没闪 
                if(p1==1 && b1[1]){
                    find1(1);
                    if(p2==6){
                        if(b1[1]){find1(1);return 1;}
                        return 0;
                    }
                    return 1;
                }else{
                    return 0;
                }
            }
        }else{//玩家1对玩家2出杀 
            if(b2[2]){
                find2(2);
                if(p1==6){//对方吕布 
                    if(b2[2]){
                        find2(2);return 1;
                    }else{//没闪 
                        if(p2==1 && b2[1]){find2(1);return 1;}
                        return 0;   
                    }
                }else{
                    return 1;
                }
            }else{//没闪 
                if(p2==1 && b2[1]){
                    find2(1);
                    if(p1==6){
                        if(b2[1]){find2(1);return 1;}
                        return 0;
                    }
                    return 1;
                }else{
                    return 0;
                }
            }
        }
    }

    树上问题

    CCPC高职场L

    SOLUTION

    树上背包

    CODE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    #include <bits/stdc++.h>

    using namespace std;
    const int N = 3e3 + 10, inf = 0x3f3f3f3f;

    int a[N], dp0[N][N], dp1[N][N], ans0[N], ans1[N], pd[N][N], n;
    int tmp0[N], tmp1[N];
    vector<int> e[N];

    int dfs(int u, int fa){
    	int sz = a[u];
    	int p = a[u];
    	if(a[u]){
    		dp0[u][1] = dp1[u][1] = 0;
    	}
    	for(int i : e[u]){
    		if(i == fa) continue;
    		int p = dfs(i, u);
            for(int j = 0; j <= sz; j++) tmp0[j] = dp0[u][j], tmp1[j] = dp1[u][j];
    		for(int j = 1; j <= p; j++){
    			for(int k = j + sz; k >= j + a[u]; k--){
    				dp0[u][k] = min(dp0[u][k], dp0[i][j] + tmp0[k - j] + 2);
                    if(k - j > 0){
                        dp1[u][k] = max(dp1[u][k], dp1[i][j] + max(tmp1[k - j], pd[u][k - j]) + 2);
                    }
    			}
    		}
            for(int j = 1; j <= p; j++){
                pd[u][j] = max(pd[u][j], dp1[i][j] + 2);
            }
    		sz += p;
    	}
    	for(int i = 1; i <= sz; i++){
    		ans0[i] = min(ans0[i], dp0[u][i]);
    		ans1[i] = max(ans1[i], dp1[u][i]);
    	}
    	// dbg(u);
    	for(int i = 1; i <= sz; i++){
            // dbg(i, dp1[u][i]);
    		dp1[u][i] = max(dp1[u][i], pd[u][i]);
            // dbg(i, dp1[u][i]);
    	}
        // puts("");
    	return sz;
    }

    void solve(){
    	scanf("%d", &n);
    	for(int i = 1; i <= n; i++){
    		scanf("%d", &a[i]);
    		ans0[i] = inf;
    		ans1[i] = -inf;
    		for(int j = 1; j <= n; j++){
    			dp0[i][j] = inf;
    			dp1[i][j] = pd[i][j] = -inf;
    		}
    	}
    	for(int i = 0, u, v; i < n - 1; i++){
    		scanf("%d%d", &u, &v);
    		e[u].push_back(v);
    		e[v].push_back(u);
    	}
    	int res = dfs(1, 0);
    	for(int i = 1; i <= n; i++){
    		if(i > res){
    			puts("-1 -1");
    		}else{
    			printf("%d %d\n", ans1[i], ans0[i]);
    		}
    	}
    }

    int main(){
    	int T = 1;
    	while(T--) solve();
    	return 0;
    }

    Monkey Joe

    SOLUTION

    考虑计算每个点产生的贡献

    经过手玩数据以及胡乱推导可以发现, 对于一个点$x$, 它所产生的贡献为

    因此$y$可以分为以下三类:

    1. $y$在$x$的子树中
    2. $y$为$x$的祖先
    3. 其他

    对于第一类, 枚举$x$的每一个儿子, 计算该儿子的子树里合法的$y$的贡献即可, 这个贡献值为

    至于快速计算上面这个式子的值, 可以用主席树

    对于第二类, 在$dfs$的过程中可以顺便记录$x$的祖先信息, 可以用树状数组维护, 贡献值式子和上面那个差不多

    对于第三类, 其实就是那些满足$Val_y \le Val_x$条件且不为$x$子树或祖先的$y$, 贡献值为${size_x}\sum{size_y}$

    这个式子中的$\sum{size_y}$可以用所有的符合条件的总和减去在子树中的和祖先中的部分

    除此之外, 要注意在第一类中$y$是可以等于$x$的, 此时的路径个数可以分成两部分计算(路径两端点都在$x$子树中和一端在子树中另一端不在子树中)

    CODE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    #include <bits/stdc++.h>

    using namespace std;

    typedef long long ll;
    const int N = 5e5 + 10, mod = 1e9 + 7;
    int root[N], tot = 0, num[N], len, a[N];
    struct Info {
        int sum, l, r;
    } info[N << 5];

    int getid(int x) {
        return lower_bound(num + 1, num + len + 1, x) - num;
    }

    void build(int &x, int l, int r) {//创建空树
        x = ++tot;
        info[x].sum = 0;
        if (l == r) return;
        int mid = (l + r) / 2;
        build(info[x].l, l, mid);
        build(info[x].r, mid + 1, r);
    }

    void update(int pre, int &now, int l, int r, int q, int x) {//更新
        now = ++tot;
        info[now] = info[pre];
        info[now].sum += x;
        info[now].sum %= mod;
        if (l == r) return;
        int mid = (l + r) / 2;
        if (mid >= q) update(info[pre].l, info[now].l, l, mid, q, x);
        else update(info[pre].r, info[now].r, mid + 1, r, q, x);
    }

    int query_sum(int pre, int now, int l, int r, int k) {// 求小于等于k的个数
        if (l == r) return (info[now].sum - info[pre].sum + mod) % mod;
        int mid = (l + r) >> 1;
        if (k <= mid) return query_sum(info[pre].l, info[now].l, l, mid, k);
        else return ((info[info[now].l].sum - info[info[pre].l].sum + mod) % mod + query_sum(info[pre].r, info[now].r, mid + 1, r, k)) % mod;
    }

    vector<int> e[N];
    int lu[N], ru[N], id[N], pid, sz[N], ans, n, inv2 = 500000004, prex[N];

    void dfs(int u, int fa){
        lu[u] = ++pid;
        id[pid] = u;
        sz[u] = 1;
        for(int i : e[u]){
            if(i == fa) continue;
            dfs(i, u);
            sz[u] += sz[i];
        }
        ru[u] = pid;
    }

    template <typename T>
    struct Fenwick {
        const int n;
        vector<T> a;
        Fenwick(int n) : n(n), a(n + 1) {}
        void add(int x, T v) {
            while(x <= n){
                a[x] += v;
                a[x] %= mod;
                x += x & -x;
            }
        }
        T sum(int x) {
            T ans = 0;
            for (int i = x; i; i -= i & -i) {
                ans += a[i];
                ans %= mod;
            }
            return ans;
        }
        T rangeSum(int l, int r) {
            return (sum(r) - sum(l - 1) + mod) % mod;
        }
    };

    Fenwick<int> fsum(N), fcnt(N), fdp(N);

    void run(int u, int fa){
        int pos = getid(a[u]), cnt = fcnt.sum(pos);
        // 祖先
        ll sum = 0, sum1 = ((1ll * cnt * n % mod - fdp.sum(pos)) + mod) % mod * sz[u] % mod;
        // 非祖先 非子树
        ll sum2 = prex[pos] - query_sum(root[lu[u] - 1], root[ru[u]], 1, len, pos);
        sum2 -= fsum.sum(pos);
        sum2 %= mod;
        if(sum2 < 0) sum2 += mod;
        sum2 = sum2 * sz[u] % mod;
        // 子树
        ll sum3 = 1ll * (sz[u] - 1) * (sz[u] - 2) % mod * inv2 % mod, sum4 = 0; // u - u
        sum3 = (sum3 + 1ll * (n - sz[u] + 1) * sz[u] % mod) % mod;
        for(int i : e[u]){
            if(i == fa) continue;
            sum4 += 1ll * (n - sz[i]) * query_sum(root[lu[i] - 1], root[ru[i]], 1, len, pos);
            sum4 %= mod;
            sum3 -= 1ll * (sz[i] - 1) * sz[i] % mod * inv2 % mod;
            sum3 %= mod;
            if(sum3 < 0) sum3 += mod;
        }
        //dbg(u);
        //dbg(sum1, sum2, sum3, sum4);
        sum = (sum1 + sum2 + sum3 + sum4) % mod;
        //dbg(sum);
        sum = sum * a[u] % mod;
        ans = (ans + sum) % mod;
        fcnt.add(pos, 1);
        fsum.add(pos, sz[u]);
        for(int i : e[u]){
            if(i == fa) continue;
            fdp.add(pos, sz[i]);
            run(i, u);
            fdp.add(pos, -sz[i]);
        }
        fsum.add(pos, -sz[u]);
        fcnt.add(pos, -1);
    }

    void solve() {
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i], num[i] = a[i];
        for(int i = 0, u, v; i < n - 1; i++){
            cin >> u >> v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs(1, 0);
        sort(num + 1, num + 1 + n);
        len = unique(num + 1, num + 1 + n) - num - 1;
        build(root[0], 1, len);
        for(int i = 1; i <= pid; i++){
            int p = getid(a[id[i]]);
            update(root[i - 1], root[i], 1, len, p, sz[id[i]]);
            prex[p] = sz[id[i]];
        }
        for(int i = 1; i <= n; i++){
            prex[i] += prex[i - 1];
            prex[i] %= mod;
        }
        run(1, 0);
        cout << ans;
    }

    int main() {
        int T = 1;
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        // cin >> T;
        while (T--) solve();
        return 0;
    }
    本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可