646 div2

复盘：本场签到题AB写的略慢，B甚至没把思路考虑清楚，就开始动键盘，E题也没把思路考虑完整清楚。之前自身出现的问题是不懂一个思路遇到挫折就换一个思路，现在是没把思路考虑完整，结合样例考虑（正式比赛中还需要这样自己想样例的能力）。

A.Odd Selection

思路：我的思路统计奇数偶数个数的情况，只有奇数个奇数才能满足此题条件，但是在这个条件的基础上还需要满足他的个数符合要求，标程写的还是也还挺好的，但是像我就是会考虑个数的关系，其实没有利用好计算机的特点；

int a[N];
 
int main(){
    int T; scanf("%d" , &T);
    for(int cas = 1 ; cas <= T ; cas ++){
        int n , m ;
        scanf("%d %d" , &n , &m);
        int res1 = 0 ,res2 = 0;
        for(int i = 1 ; i <= n ; i ++){
            scanf("%d" ,&a[i]);
            if(a[i] % 2 == 1) res1 ++;
            else res2 ++;
        }
        if(res1 == 0){
            puts("No");
            continue;
        }
        if(m % 2 == 0){
            if(res2 == 0){
                puts("No");
                continue;
            }
            if(res1 % 2 == 0){
                if(res1 - 1 + res2 >= m)puts("Yes");
                else puts("No");
            }
            else puts("Yes");
        }
        else{
            if(res1 % 2 == 0){
                if(res1 - 1 + res2 >= m)puts("Yes");
                else puts("No");
            }
            else puts("Yes");
        }
    }
    return 0;
}

B.Subsequence Hate

思路：没考虑清楚的题之一，明明是00001111或者1111000的情况，但是却只考虑了一个1；

int main(){
    int T; scanf("%d" , &T);
    for(int cas = 1 ; cas <= T ; cas ++){
        string a;
        cin >> a;
        int ans = inf;
        for(int i = 0 ; i <= SZ(a) ; i ++){
            int res = 0 ,res1 = 0 ;
            for(int j = i - 1;j >= 0 ; j --){
                if(a[j] == '0') res ++;
                else res1 ++;
            }
            for(int j = i ; j < SZ(a) ; j ++){
                if(a[j] == '1') res ++;
                else res1 ++;
            }
            ans = min(ans, res);
            ans = min(ans, res1);
        }
        printf("%d\n",ans);
 
    }
    return 0;
}

C. Game On Leaves

思路：可以理解为小博弈，除了关键节点剩下的ans个点再减1判断奇偶，刚刚看了题解，我好像个小傻子，明明只需判断就可以了，还写了dfs。另附题解代码。

vector<int>v[N];
int sz[N];
void dfs(int x,int fa = -1){
    sz[x] = 1;
    for(auto y :v[x]){
        if(y == fa)continue;
        dfs(y ,x);
        sz[x] += sz[y];
    }
}
int main(){
    int T; scanf("%d" , &T);
    for(int cas = 1 ; cas <= T ; cas ++){
        int n ,pos;
        scanf("%d %d" , &n, &pos);
        for(int i = 1; i <= n ; i ++)v[i].clear();
        for(int i = 1; i < n ; i ++){
            int x, y;
            scanf("%d %d" , &x , &y);
            v[x].pb(y);
            v[y].pb(x);
        }
        dfs(pos);
        int maxx = -1 , ans = 0;
        for(auto y : v[pos]){
            maxx = max(sz[y] , maxx);
            ans += sz[y];
        }
        if(SZ(v[pos]) == 1){
            puts("Ayush");
        }
        else{
            if((ans - 1)%2 == 1){
                puts("Ashish");
            }
            else{
                puts("Ayush");
            }
        }
    }
    return 0;
}

const int N = 2e5 + 5;
 
int n, x;
int deg[N];
vector<int> g[N];
 
int32_t main()
{
	IOS;
	int t;
	cin >> t;
	while(t--)
	{
		memset(deg, 0, sizeof(deg));
		cin >> n >> x;
		for(int i = 1; i <= n - 1; i++)
		{
			int u, v;
			cin >> u >> v;
			deg[u]++, deg[v]++;
		}
		if(deg[x] <= 1)
			cout << "Ayush" << endl;
		else
		{
			if(n % 2)
				cout << "Ashish" << endl;
			else
				cout << "Ayush" << endl;
		}
	}
	return 0;
}

D. Guess The Maximums

未补！！！！！！！！

E. Tree Shuffling

题意：根为1的树，对于任意一个点x，可以对这个点的子树打乱k（k为任意值）个节点的顺序，满足最后满足现有值（1 or 0）和目标相同（1 or 0）花费a[x]*k，最后的最小花费。
思路：dfs回溯，最重要的思路点是若当前的节点的花费比向上到根节点的花费的最小值还要小，那么就优先把此节点替换一下。就是回溯合并就行了，其他没啥。

LL a[N];
int n;
int b[N], c[N];
int dp[N][3];
VI G[N];
LL ans;
void dfs(int x, int fa = -1 , LL cost = inf){
    if(b[x] != c[x]){
        dp[x][b[x]] ++;
    }
    for(auto y : G[x]){
        if(fa == y) continue;
        dfs(y , x , min(cost , a[x]));
        dp[x][0] += dp[y][0];
        dp[x][1] += dp[y][1];
    }
    LL res = min(dp[x][0], dp[x][1]);
    if(a[x] <= cost){
        ans += 2*res*a[x];
        dp[x][0] -= res;
        dp[x][1] -= res;
    }
}
 
int main(){
    while(~scanf("%d" , &n)){
        memset(dp,0,sizeof dp);
        for(int i = 1; i <= n ; i ++)G[i].clear();
        for(int i = 1; i <= n ; i ++){
            scanf("%lld %d %d",&a[i] , &b[i] , &c[i]);
        }
        for(int i = 1; i < n ; i ++){
            int x,y ; scanf("%d %d" ,&x, &y);
            G[x].pb(y) ; G[y].pb(x);
        }
        ans = 0 ;
        dfs(1);
        if(dp[1][0] + dp[1][1])puts("-1");
        else printf("%lld\n",ans);
    }
}