题解 CF743D 【Chloe and pleasant prizes】

前言

思想：树链剖分

算法：一道不太难的换根(换根?感觉不算是)+线段树

难度:3星

首先我们明确一个众所周知的事情：

一个子树的(不是欧拉序！)序是连续的，子树的根节点的序是最小的。

然后这个子树中最大的序为

(写过树链剖分的都知道吧。)

思路

因为只需要选择出两个，所以考虑枚举其中一棵子树，然后求最大的和当前字树没有重复节点的一棵子树。

考虑每次我们向儿子换根，因为每一次换根后，我们能够选择的子树的数量相对与没换之前是不断在增加的，这样子比较好维护状态。

新的可以选择的子树有哪些？

不难发现，新的 可以选择的子树 即:

当前节点的父亲节点为根的子树内，

除了当前点为根的子树内的所有点以及当前节点的父亲节点以外的所有节点。

你可以画一个图进行理解这句话。这一句话至关重要，是这个做法的核心！

然后我们发现，我们需要求最大值的区间被分为了两段：

每次能选择的子树只会加入一些新的子树而不需要删除一些子树，所以只需要比较现在能够选择的最大值与新加入的一些子树的最大值即可。

采用DFS的方式，将目前最大值作为一个参数传递，这样子方便更新，也不需要回溯。

注意要预处理一下每一棵子树的权值和，在预处理DFS的时候记录一下每一棵子树有多少个子节点以及子树的权值和。

这道题就做完了

具体可以看一看代码:

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int MAXN = 200005,INF = 1000000000000000000;
int n;
int a[MAXN],dfn[MAXN],sum[MAXN],now = 0;
int start[MAXN],cnt = 0,dfn_id[MAXN],siz[MAXN],Ans = -INF;

//sum[x]表示点x的子树权值和
//dfn[x]表示点x的dfn序
//a[x]表示点x一开始的权值
//siz[x]表示以x为根的子树内一共多少个点
//dfn_id[x]表示dfn序为x的点是哪一个

struct Edge {
    int next,to;
} edge[MAXN * 2];

struct Segment {
    int l,r,Max;    //普通线段树
} T[MAXN * 4];

inline int read()
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar())if(ch == '-')flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar())x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

void add(int from,int to)
{
    cnt ++;
    edge[cnt].to = to;
    edge[cnt].next = start[from];
    start[from] = cnt;
    return ;
}

int DFS(int x,int from)
{
    siz[x] = 1;
    now ++;
    dfn[x] = now;
    dfn_id[now] = x;
    for(int i = start[x] ; i ; i = edge[i].next)
    {
        int to = edge[i].to;
        if(to != from && dfn[to] == 0)siz[x] += DFS(to,x);
    }
    return siz[x];
}

int DFS2(int x,int from)
{
    sum[x] = a[x];
    for(int i = start[x] ; i ; i = edge[i].next)
    {
        int to = edge[i].to;
        if(to != from)sum[x] += DFS2(to,x);
    }
    return sum[x];
}

void build(int x,int l,int r)
{
    T[x].l = l , T[x].r = r ;
    if(l == r){T[x].Max = sum[dfn_id[l]] ; return ;}
    int mid = ( l + r ) >> 1;
    build(x << 1 , l, mid);
    build(x << 1 | 1 , mid + 1 , r);
    T[x].Max = max(T[x << 1].Max , T[x << 1 | 1].Max);
    return ;
}

int GetMax(int x,int l,int r)
{
    if(l > r)return -INF;
    int Max = -INF;
    if(T[x].l >= l && T[x].r <= r)return T[x].Max;
    int mid = (T[x].l + T[x].r) >> 1;
    if(l <= mid)Max = max(Max,GetMax(x << 1 , l, r));
    if(r  > mid)Max = max(Max,GetMax(x << 1 | 1 , l , r));
    return Max;
}//线段树找最大值的板子

void Get_Ans(int x,int from,int Max)
{
    if(x != 1)
    {
        int l = dfn[from],r = dfn[from] + siz[from] - 1;
        int L = dfn[x] , R = dfn[x] + siz[x] - 1;
        Max = max((GetMax(1,l + 1,L - 1),GetMax(1,R + 1 , r)),Max);
        //更新最大值，当前点的儿子节点都会用这个最大值
        //l+1是因为当前点的根节点不能选,L-1是因为子树ｘ内的点不能选
        //R + 1是因为Ｒ仍然是子树x内的最大dfn序，被子树x包含了
        if(Max != -INF)
        Ans = max(sum[x] + Max,Ans);
    }
    for(int i = start[x] ; i ; i = edge[i].next)
    {
        int to = edge[i].to;
        if(to != from)Get_Ans(to,x,Max);//换根为自己的儿子节点
    }
    return ;
}

signed main()
{
    n = read();
    for(int i = 1 ; i <= n ; i ++)a[i] = read();
    for(int i = 1 ; i <= n - 1 ; i ++)
    {
        int u = read(), v = read();
        add(u,v);
        add(v,u);
    }
    DFS(1,0);//预处理dfn数组,dfn_id数组以及siz数组
    DFS2(1,0);//预处理sum数组
    build(1, 1 , n);
    Get_Ans(1,0,-INF);//换根获得答案
    if(Ans >= -1e14)cout << Ans;
    else cout << "Impossible";//如果答案过小显然不合法，
    return 0;
}