【题解】Atcoder ARC#83 E-Bichrome Tree
标签：div mes etc chrome || 取值 自己 add pos
哈哈~自己做出来的E题！（虽然这题被机房大佬强D极水）。最开始神经错乱，写了个完全不对的贪心，竟然只错了4个点(?•ˇ?ˇ•?)
可以发现，一个节点的子树内部和他颜色相同的节点权值和 是固定的，那么不一定的就是另外的那个颜色的权值和了。而由于这个图上权值可以从 0 开始取值，显然越小越好。这样就可以dp啦。
其实我这个里面多了一个维度，就是记录当节点为黑色/白色时怎么怎么样，但其实这两个状态完全对称，根本没必要再多开一个维。但我就懒得改啦~
#include using namespace std;
#define maxn 6000
#define INF 999999999
int n, W[maxn], f[2][2][maxn], g[maxn][2];
int read()
{
int x = 0, k = 1;
char c; c = getchar();
while(c ‘0‘ || c > ‘9‘) { if(c == ‘-‘) k = -1; c = getchar(); }
while(c >= ‘0‘ && c ‘9‘) x = x * 10 + c - ‘0‘, c = getchar();
return x * k;
}
struct edge
{
int cnp, to[maxn], last[maxn], head[maxn];
edge() { cnp = 2; }
void add(int u, int v) { to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++; }
}E1;
bool Down(int &x, int y)
{
if(y >= INF) return 0;
x = min(x, y); return 1;
}
void dfs(int u)
{
for(int i = E1.head[u]; i; i = E1.last[i]) { int v = E1.to[i]; dfs(v); }
for(int i = 0; i 1; i ++)
for(int j = 0; j 0][i][j] = INF;
f[0][0][0] = f[0][1][0] = 0; int pre = 0, now = 1;
for(int i = E1.head[u]; i; i = E1.last[i])
{
int v = E1.to[i];
for(int j = 0; j 1; j ++)
for(int k = 0; k INF;
for(int k = 0; k 1; k ++)
for(int j = 0; j )
{
int flag = 0;
if(j - W[v] >= 0) flag = Down(f[now][k][j], f[pre][k][j - W[v]] + g[v][k]);
if(j - g[v][k ^ 1] >= 0) flag = Down(f[now][k][j], f[pre][k][j - g[v][k ^ 1]] + W[v]);
}
swap(pre, now);
}
g[u][0] = g[u][1] = INF;
for(int k = 0; k 1; k ++)
for(int j = 0; j )
g[u][k] = min(g[u][k], f[pre][k][j]);
}
int main()
{
n = read();
for(int i = 2; i int x = read(); E1.add(x, i); }
for(int i = 1; i read();
dfs(1);
if(g[1][0] 1][1] "POSSIBLE\n");
else printf("IMPOSSIBLE\n");
return 0;
}
【题解】Atcoder ARC#83 E-Bichrome Tree
标签：div mes etc chrome || 取值 自己 add pos
原文地址：https://www.cnblogs.com/twilight-sx/p/9733823.html
评论