1 条题解

  • 0
    @ 2026-5-5 16:24:29
    #include<bits/stdc++.h>
    #define ll long long
    #define pb emplace_back
    #define N 300010
    using namespace std;
    struct nod{int l,r,y;ll v,ta;}t[N];
    vector<int> a[N];
    int rt[N],m,n,x,y,d[N],p;
    void jb(int x,int y){a[x].pb(y);}
    void ya(int x){if (t[x].ta){t[x].v+=t[x].ta;t[t[x].l].ta+=t[x].ta;t[t[x].r].ta+=t[x].ta;t[x].ta=0;}}
    int me(int x,int y){
    	if (!x||!y) return x|y;
    	ya(x);ya(y);
    	if (t[x].v>t[y].v) swap(x,y);
    	if(rand()%2)swap(t[x].l,t[x].r);
    	t[x].r=me(t[x].r,y);
    	return x;
    }
    void dfs(int x,int fa){
    	d[x]=d[fa]+1;
    	ll mi=0;
    	for (auto y:a[x]){
    		if (y!=fa){
    			dfs(y,x);
    			while (d[t[rt[y]].y]>d[x])rt[y]=me(t[rt[y]].l,t[rt[y]].r);
    			if (rt[y]==0)p=1;
    			mi+=t[rt[y]].v;
    		}
    	}
    	t[rt[x]].ta+=mi;
    	for (auto y:a[x]){if (y!=fa){t[rt[y]].ta+=mi-t[rt[y]].v;rt[x]=me(rt[x],rt[y]);}}
    }
    int main(){
    	cin>>n>>m;
    	for (int i=1;i<n;i++){cin>>x>>y;jb(x,y);jb(y,x);}
    	for (int i=1;i<=m;i++){cin>>x>>t[i].y>>t[i].v;if (x!=t[i].y)rt[x]=me(rt[x],i);}
    	dfs(1,0);
    	if (p)puts("-1");else {ya(rt[1]);cout<<t[rt[1]].v<<endl;}
    	return 0;
    }
    
    • 1

    信息

    ID
    6872
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者