可否麻烦各位大牛看一下究竟这组代码到底是在哪里RE的? 是因为递回过深吗!? 难道记忆化搜索也无法吗...

#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<utility>
#include<functional>
#include<algorithm>
#define PB push_back
#define MP make_pair
#define _F first
#define _S second

using namespace std;

typedef long long int ll;
typedef pair<int, ll> pii;
const long long int INF = 2000000000;
vector<pii> Edge[200200];
long long int DP1[200200], DP2[200200];
int root, par[200200], parS[200200];
long long int con[200200];

void init(void){
    for(int i = 0; i < 200100; i++){
        if(Edge[i].size()) Edge[i].clear();
        DP1[i] = 0;
        DP2[i] = -1;
        con[i] = 0;
        parS[i] = 0;
        par[i] = 0;
        root = 0;
        }
    return;
    }

ll __MN(ll A, ll B){
    if(A > B) return B;
    return A;
    }
ll __MX(ll A, ll B){
    if(A > B) return A;
    return B;
    }

void DFS1(int now, int pre){
    par[now] = pre;
    if(now!=root && Edge[now].size()==1){
        DP1[now] = INF;
        return;
        }
    for(int i = 0; i < Edge[now].size(); i++){
        pii nxt = Edge[now][i];
        
        if(nxt._F == pre) continue;
        parS[nxt._F] = nxt._S;
        DFS1(nxt._F, now);
        con[nxt._F] = __MN(DP1[nxt._F], nxt._S);
        DP1[now] += con[nxt._F];
        if(DP1[nxt._F] == INF) DP1[nxt._F] = 0;
        }
    return;
    }

void DFS2(int now){
    
    if(now == root) return;//if(now < 0) while(1);
    if(now < 0) return;
    if(par[now] < 0) return;
    
    if(DP2[now] != -1) return;
    if(DP2[par[now]] == -1) DFS2(par[now]);
    if(Edge[now].size() == 1){
        DP2[now] = __MN(Edge[now][0]._S, DP2[par[now]]);
        return;
        }
    if(par[now]==root && Edge[par[now]].size()==1){
        DP2[now] = Edge[par[now]][0]._S+DP1[now];
        return;
        }
    DP2[now] = __MN(DP2[par[now]]-con[now], parS[now])+DP1[now];

    return;
    }

int main(void){
    int T;
    srand(time(NULL));
    scanf("%d", &T);

    while(T--){
        int N, x, y;
        long long int z;
        scanf("%d", &N);
        init();
        for(int i = 0; i < N-1; i++){
            scanf("%d%d%lld", &x, &y, &z);
            Edge[x].PB(MP(y, z));
            Edge[y].PB(MP(x, z));
            }
        root = rand()%N;
        root++;
        
        par[root] = -1;
        DFS1(root, -1);
        
        
        DP2[root] = DP1[root];
        
        for(int i = 1; i <= N; i++) DFS2(i);
        
        long long int ans = 0;
        for(int i = 1; i <= N; i++)
            ans = __MX(ans, DP2[i]);
        printf("%lld\n", ans);
        }

    return 0;
    }

• Re:RE? 不了解... (2986) happyZYMak 2019-08-05 09:52:13