PLCT检查是什么洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化／wqs二分)

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#define Pair pair<int, int>
#define int long long 
const int MAXN = 3 * 1e5 + 1;
using namespace std;
inline int read() 
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
struct Node {
    int x, y;//x ：权值   y：数目 
    bool operator < (const Node &rhs) const {
        return this -> x == rhs.x ? this -> y > rhs.y : this -> x < rhs.x;//tag
    }
    Node operator + (const Node &rhs) const {
        return (Node) {x + rhs.x, y + rhs.y};
    }
    Node operator + (const int &rhs) const {
        return (Node) {x + rhs, y};
    }
}f[3][MAXN];
int N, K;
struct Edge {
    int u, v, w, nxt;
}E[MAXN << 1];
int head[MAXN], num = 0;
inline void AddEdge(int x, int y, int z) {
    E[num] = (Edge) {x, y, z, head[x]};
    head[x] = num++;
}
int mid;
Node Plus(Node a) {
    return (Node){a.x - mid, a.y + 1};
}
void dfs(int x, int fa) {
    f[2][x] = max(f[2][x], (Node) {-mid, 1});
    for(int i = head[x]; i != -1; i = E[i].nxt) 
    f[0][x] = max(f[0][x], max(Plus(f[1][x]), f[2][x]));
}
main() 
    l = -r;
    while(l <= r) 
    mid = l; memset(f, 0, sizeof(f));
    dfs(1, 0);
    printf("%lld", f[0][1].x + mid * K);
    return 0;
}