51nod"省选"模测 A 树的双直径(树形dp)

题意

题目链接

Sol

比赛结束后才调出来。。不多说啥了,就是因为自己菜。

裸的up-down dp,维护一下一个点上下的直径就行,一开始还想了个假的思路写了半天。。

转移都在代码注释里

毒瘤题目卡空间

#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define LL long long 
using namespace std;
const int MAXN = 6e5 + 10;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A> inline void debug(A a){cout << a << '\n';}
template <typename A> inline LL sqr(A x){return 1ll * x * x;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
void print(__int128 x) {
    if (x>9) print(x/10);
    putchar('0'+x%10);
}
int N, p[MAXN * 2], ve[MAXN * 2];
long long f[MAXN], g[MAXN], mxpre[MAXN], mxsuf[MAXN], dl[MAXN], ul[MAXN];
__int128 ans;
vector<Pair> v[MAXN];
void downdfs(int x, int fa) {
    f[x] = dl[x] = 0;
    for(auto &tp : v[x]) {
        int to = tp.fi, w = tp.se;
        if(to == fa) continue;
        downdfs(to, x);
        chmax(dl[x], f[x] + f[to] + w);
        chmax(f[x], f[to] + w);
        chmax(dl[x], dl[to]);
    }
}

void updfs(int x, int fa) {
    int cnt = 0;
    for(int i = 0; i < v[x].size(); i++) 
        if(v[x][i].fi != fa) p[++cnt] = v[x][i].fi, ve[cnt] = v[x][i].se;
    
    mxpre[0] = 0; mxsuf[cnt + 1] = 0;
    for(int i = 1; i <= cnt; i++) mxpre[i] = max(mxpre[i - 1], f[p[i]] + ve[i]);
    for(int i = cnt; i >= 1; i--) mxsuf[i] = max(mxsuf[i + 1], f[p[i]] + ve[i]);
    //一个点向上的直径:
    //1: 从父亲的ul继承过来
    //2: 前后缀中的最大值f + 出边 + 入边
    //3: 父亲的g + 兄弟节点中最大的f + 出边 
    //4: 前驱/后继 中的最大和次大
    //5: 前驱/后继 中的子树中的直径 

    for(int i = 1; i <= cnt; i++) {
        int to = p[i], w = ve[i];
        chmax(g[to], g[x] + w);
        chmax(g[to], max(mxpre[i - 1], mxsuf[i + 1]) + w);
        chmax(ul[to], ul[x]);//1
        chmax(ul[to], mxpre[i - 1] + mxsuf[i + 1]);//2
        chmax(ul[to], g[x] + max(mxpre[i - 1], mxsuf[i + 1]));//3
    }
    
    long long mx1 = -1e18, mx2 = -1e18, mx3 = -1e18;
    for(int i = 1; i <= cnt; i++) {
        chmax(ul[p[i]], max(mx1 + mx2, mx3)); int tmp = f[p[i]] + ve[i];
        if(tmp > mx1) chmax(mx2, mx1), mx1 = tmp;
        else if(tmp > mx2) mx2 = tmp;
        chmax(mx3, dl[p[i]]);
    }
    mx1 = -1e18, mx2 = -1e18, mx3 = -1e18;
    for(int i = cnt; i >= 1; i--) {
        chmax(ul[p[i]], max(mx1 + mx2, mx3)); int tmp = f[p[i]] + ve[i];
        if(tmp > mx1) chmax(mx2, mx1), mx1 = tmp;
        else if(tmp > mx2) mx2 = tmp;
        chmax(mx3, dl[p[i]]);
    }
    
    for(int i = 0; i < v[x].size(); i++) 
        if(v[x][i].fi != fa) updfs(v[x][i].fi, x);
        
}
signed main() {
    //freopen("a.in", "r", stdin);
    N = read();
    for(int i = 1; i <= N - 1; i++) {
        int x = read(), y = read(), w = read();
        v[x].push_back(MP(y, w));
        v[y].push_back(MP(x, w));
    }
    downdfs(1, 0);
    updfs(1, 0);
    for(int i = 2; i <= N; i++) chmax(ans, (__int128) dl[i] * ul[i]);
    
    for(int i = 1; i <= N; i++) for(auto &tp : v[i]) tp.se = -tp.se;
    memset(ul, 0, sizeof(ul)); 
    memset(g, 0, sizeof(g));
    downdfs(1, 0);
    updfs(1, 0);
    for(int i = 2; i <= N; i++) chmax(ans, (__int128) dl[i] * ul[i]);
    print(ans);
    //cout << ans;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MasiMaro 的技术博文

C语言中处理结构体的原理

汇编中有几种寻址方式,分别是直接寻址:(ds:[idata])、寄存器间接寻址(ds:[bx])、寄存器相对寻址(ds:[bx + idata]、ds:[bx ...

15620
来自专栏JAVA同学会

JAVA9模块化详解(一)——模块化的定义

java9已经出来有一段时间了,今天向大家介绍一下java9的一个重要特性——模块化。模块化系统的主要目的如下:

10310
来自专栏木溪知识加油站

笔记——四大组件(十五)

1、Activity是一种展示型组件。Activity的启动由Intent触发,其中Intent可以分为显式Intent和隐式Intent,显式Intent可以...

10720
来自专栏MasiMaro 的技术博文

COM学习(三)——COM的跨语言

COM是基于二进制的组件模块,从设计之初就以支持所有语言作为它的一个目标,这篇文章主要探讨COM的跨语言部分。

24540
来自专栏MasiMaro 的技术博文

算法与数据结构(一):时间复杂度与空间复杂度

最近突然萌生了一个想法,好好系统的学习一下算法与数据结构然后产生一系列的文章来回顾与总结学到的东西,这部分我想从最简单的部分一一介绍总结,包括一些很基础的内容 ...

10710
来自专栏MasiMaro 的技术博文

向上取整算法

在进行内存分配的时候一般都需要在实际使用内存大小的基础上进行内存对齐,比如一般32位平台进行4字节对齐,而64位平台使用8字节对齐等等。 一般采用的算法是先利...

16320
来自专栏MasiMaro 的技术博文

缓冲区溢出漏洞

缓冲区溢出的根本原因是冯洛伊曼体系的计算机并不严格的区分代码段和数据段,只是简单的根据eip的指向来决定哪些是代码,所以缓冲区溢出攻击都会通过某种方式修改eip...

33720
来自专栏MasiMaro 的技术博文

C++多态

面向对象的程序设计的三大要素之一就是多态,多态是指基类的指针指向不同的派生类,其行为不同。多态的实现主要是通过虚函数和虚表来完成,虚表保存在对象的头四个字节,要...

10920
来自专栏木溪知识加油站

笔记——安卓消息机制Handler(十六)

1、定义:Android的消息机制主要是指Handler的运行机制,Handler并不是专门用于更新UI的,它只是常被开发者用来更新UI,是同一个进程中线程间的...

12440
来自专栏MasiMaro 的技术博文

COM学习(四)——COM中的数据类型

上一次说到,COM为了跨语言,有一套完整的规则,只要COM组件按照规则编写,而不同的语言也按照对应的规则调用,那么就可以实现不同语言间相互调用。但是根据那套规则...

9330

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励