1 条题解
-
0
#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
- 上传者