http://codeforces.com/contest/429

A题dfs即可,传入5个参数:now, father, deep, oddDeepCnt, evenDeepCnt,详见代码。
D题将g(i,j)视作前缀和之差(sum[j]-sum[i]),则问题转化为求(i,sum[i])的最近点对问题。

A

/*93ms,6296KB*/

const int mx = 100005;

vector<int> g[mx], ans;
int init[mx], goal[mx];

void dfs(int now, int fa, int deep, int cnt0, int cnt1)
{
    if (deep & 1) {if ((init[now] + cnt1 - goal[now]) & 1) ++cnt1, ans.PB(now);}
    else {if ((init[now] + cnt0 - goal[now]) & 1) ++cnt0, ans.PB(now);}
    int i;
    For(i, g[now].size()) if (g[now][i] != fa) dfs(g[now][i], now, deep + 1, cnt0, cnt1);
}

int main()
{
    int n, i, a, b;
    SI(n);
    For(i, n - 1) SII(a, b), g[a].PB(b), g[b].PB(a);
    SA(init + 1, i, n);
    SA(goal + 1, i, n);
    dfs(1, 0, 0, 0, 0);
    PI(ans.size());
    PAn(ans, i, ans.size());
    return 0;
}

Comments

comments powered by Disqus