Black Magic

题目大意：
给定n个方块，每个方块左右都可能是黑色或者白色，具体如下
E：左右两边都是白***r>L：左边是黑色，右边是白***r>R：右边是白色左边是黑***r>B：左右两边都是黑***r>给定每种方块的数量
如果相邻的两个方块邻面颜色都是黑色，那么这两个方块就可以合并
求出经过处理之后最少的方块数和最大的方块数

input：
3
1 1 1 1
1 2 3 4
3 4 5 6

output：
2 4
4 8
8 16

解：
对于连通块最多的情况，我们需要让合并的方块尽可能的少
可以把L全放在最左边，R全放在最右边，然后E和B相间摆放
对于连通块最少的情况
可以先把B全合并起来，一个L和一个R也能分为一组拼起来，注意，如果有B并且有一组L和R的话，可以把一组L和R拼在B的两边，这样可以再减少一组。

#include <bits/stdc++.h>
using namespace std ;
#define ll long long 
#define endl '\n'

int p,q,i,j;

ll solve2(int a,int b,int c,int d) {
    ll ans = 0;
    /*int aa=0,dd=0;
    int minn = min(c,b);
    aa = min(minn,a);
    b -= aa, c -= aa;
    minn = min(c,b);
//    dd= min(minn,d) ;
//    cout<<"dd is "<<dd<<endl;
//    b -= dd,c -=dd;
    int l = min(b,c);
    ans += 2*l;
    ans += 2*(aa+dd);
    /*if(b!=c) {
        aa += min(b,c);
        b -= min(b,c);
        c -= min(b,c);
        ans += max(b,c) - 1;
        a++;
        if(d>a) ans--;
    } 
    //if(b==c) ans+=b*2;

    ans += min(a,d)*2;
    if(a>d) ans+=a-d;
    if(d>a && a!=0) ans+=1; 
    */
    ans += c + b ;
    if(d>a) ans+=2*a+1;
    else ans += a+d; 
//    cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl;
//    cout<<aa<<" "<<dd<<" "<<endl;
    return ans;
}
ll solve1(int a,int b,int c,int d) {
    swap(a,d);
    ll ans = 0; 
    if(a>0) a=1;
    if(b>0 || c>0) a=0;
    ans += d + a + max(b,c);
    return ans;
}
void solve() {
    cin>>p>>q>>i>>j;
    cout<<solve1(p,q,i,j)<<" "<<solve2(p,q,i,j)<<endl;
}

int main () {
    ios::sync_with_stdio(false) ,cin.tie(0);    
    int t;
    cin>>t; 
    while(t--) {
        solve();
    }
} 

Triangle Game

题目大意：
给定三个正整数abc代表三角形的三条边，两个人玩游戏，每回合需要挑选一条边并且让这条边减去>=1的值，如果在某个回合操作结束后三条边不能构成三角形，则游戏结束，问先手的人是否有必胜的策略

input：
3
2 2 3
2 3 4
5 3 4

output：
Win
Lose
Win

解：
结论：当(a-1)^(b-1)^(c-1)！=0时先手必胜

#include<bits/stdc++.h>

using namespace std;


int main() {

    int t, a, b, c;
    cin >> t;
    while (t--) {
        cin >> a >> b >> c;
        if (((a - 1) ^ (b - 1) ^ (c - 1)) != 0) {
            cout << "Win" << endl;
        } else {
            cout << "Lose" << endl;
        }
    }
}

Count Stickmen

题目大意：
给你一颗树，问你树上有多少个火柴人，如下所示

如图所示
以3,5这条骨架枚举
我们应该从一个火柴人的3，5两个部位下手
先看5下面的7和8，这是火柴人的两条腿，这是比较好求的，就是从5的所有边中减去连向3的那条边并且从剩下的边里面挑两条，用组合数计算
在看与3相连的两条手臂4,5以及9,10,这也比较好求，就是枚举3的所有邻点，将所有邻点的边数相加，最后减去3的边数，得到的结果就是与3点距离为2的点的个数，可以看图理解。但是这中点不能和5相连，因为和5相连的会是腿，所以要减去（5的边数-1）。在这些点里面选出两个点，用组合数求解。
但是如果两条手臂相同，即选到了像腿一样的两条手臂，我们必须减去这种情况，这种情况方案数就是从3的邻点中除了腿去枚举，将枚举的点的边数减一，得到的就是每个点下面有多少边，从这些边中选出两条来，最后将结果累加就是多余的情况。
选择头的话方案数明显是3的边数-3（身体和两只手臂）。

#include<bits/stdc++.h>

using namespace std;
#define int long long

vector<int> v[500005];
int edges[500005];//每个点有多少条边
int help1[500005];//du-dx
int help2[500005];//两个手臂相同的方案数
const int mod = 998244353;

int n, temp1, temp2;


int add(int a, int b) {
    return (a += b) >= mod ? a - mod : a;
}

int sub(int a, int b) {
    return (a -= b) < 0 ? a + mod : a;
}


int C(int x) {
    return x * (x - 1) / 2 % mod;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        v[i].clear();
        help1[i] = 0;
        help2[i] = 0;
        edges[i] = 0;
    }
    for (int i = 1; i <= n - 1; i++) {
        cin >> temp1 >> temp2;
        v[temp1].push_back(temp2);
        v[temp2].push_back(temp1);
        edges[temp1]++;
        edges[temp2]++;
    }
    for (int i = 1; i <= n; i++) {
        for (auto &y: v[i]) {
            help1[i] = add(help1[i], edges[y] - 1);
            help2[i] = add(help2[i], C(edges[y] - 1));
        }
//        help2[i] = sub(help2[i], C(edges[i] - 1));
    }
    int ans = 0;
    int legs, hands, head;
    for (int i = 1; i <= n; i++) {
        if (edges[i] >= 4) {//对类似样例中点3这样的点枚举，只有边数大于等于四才有可能成为点三那样的点
            for (auto &j: v[i]) {//枚举这个点所有的邻点
                if (edges[j] >= 3) {//先找到腿的节点
                    head = sub(edges[i], 3);
                    legs = sub(edges[j], 1);
                    hands = sub(help1[i], legs);
                    legs = C(legs);
                    hands = sub(C(hands), sub(help2[i], C(edges[j] - 1)));
                    ans = add(ans, head * hands % mod * legs % mod);
                }
            }
        }
    }
    cout << ans << endl;

}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}