题解 | #QQ宠物#

E:QQ宠物 解题突破点：好消息是只有n-1对NPC直接认识，并且将所有相互认识的NPC连在一起能形成一个树形的结构图。 可以发现只需要把给出的关系维护成树型结构，就可以在这棵树上跑一遍树形DP。具体的做法是用并查集维护两个人是否在同一棵树上，如果已经在同一棵树上，那就把这条边舍去。

DP[i][1]表示选了第i号节点的最大值
DP[i][0]表示不选i号节点的最大值
状态转移方程：
DP[i][1]=max(DP[i][1],DP[i][1]+DP[j][0])(j为i的儿子)选了第i号节点那它的儿子一定不能选了
Dp[i][0]=max(DP[i][0],DP[i][0]+max(DP[j][1],DP[j][0]))不选第i号节点，它的儿子可选可不选，取个最大值即可

由于最后关系会形成两棵树，所以需要跑两边dfs，同时需要注意这两棵树的根节点可能间接认识，但是其实是不能选的，所以初始化需要置为0。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int w[1000005];
int h[N], e[N], ne[N], idx;
int f[N],dp[N][2];
int find(int x)
{
    if (f[x] != x)f[x] = find(f[x]);
    return f[x];
}
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int u, int fa)
{
    dp[u][1] = w[u];
    for (int i = h[u]; i != -1; i = ne[i])//树的遍历
    {
        int j = e[i]; if (j == fa)continue;
        dfs(j, u);
        dp[u][1] += dp[j][0];//回溯时更新状态转移
        dp[u][0] += max(dp[j][0], dp[j][1]);
    }
}
int main()
{   
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> w[i];
    for (int i = 1; i <= n; i++)f[i] = i;
    int root1, root2;//最终形成两棵树的根节点
    for (int i = 1; i <= n; i++)
    {
        int a, b; cin >> a >> b;
        int fa = find(a), fb = find(b);
        if (fa == fb)
        {
            root1 = fa, root2 = fb;
            continue;
        }
        else
        {
            add(a, b), add(b, a);
        }
        f[fa] = fb;
    }
    int temp = w[root2]; w[root2] = 0;//避免间接认识
    int ans = 0;
    dfs(root1, -1);
    ans = max(dp[root1][1], dp[root1][0]);
    w[root2] = temp; w[root1] = 0;
    dfs(root2, -1);
    memset(dp, 0, sizeof dp);
    ans = max(ans, dp[root2][1]);
    ans = max(ans, dp[root2][0]);
    cout << ans << endl;




}