萌新求助,本机AC提交RE
查看原帖
萌新求助,本机AC提交RE
225991
_lxy_楼主2022/10/24 19:00

rt,后两个点都 RE 了,但是下载数据在本地都过了。

const int MAXN=5e5+7;
#define int long long
#define foredge(u) for(int ii=head[u],v=edge[ii].to,w=edge[ii].dis;ii!=-1;ii=edge[ii].nxt,v=edge[ii].to,w=edge[ii].dis)
int n,rt,a[MAXN],dp[MAXN],head[MAXN],f[MAXN],deg[MAXN];
struct Edge{
    int to,dis,nxt;
    Edge(){;}Edge(int _to,int _dis,int _nxt):to(_to),dis(_dis),nxt(_nxt){}
};vector<Edge>edge;
void add_edge(int u,int v,int w=1){edge.push_back(Edge{v,w,head[u]});head[u]=edge.size()-1;}
void dfs(int u,int fa){
    int mx=0;
    foredge(u){
        if(v==fa) continue;dfs(v,u);
        mx=qmax(mx,f[v]+w);dp[u]+=dp[v];
    }foredge(u){
        if(v==fa) continue;
        dp[u]+=mx-f[v]-w;
    }f[u]=mx;
}signed main(){
    qread(n,rt);int i,j;mem(head,-1);
    for(i=1;i<n;i++){
        int u,v,w;qread(u,v,w);
        add_edge(u,v,w);add_edge(v,u,w);
    }dfs(rt,0);printf("%lld\n",dp[rt]);
    return 0;
}
2022/10/24 19:00
加载中...