只有subtask0的一个点对,帮忙看看qwq
#include <iostream>
#include <vector>
class node
{
public:
node(long long to_=0,long long e_=0,long long w_=0):to(to_),e(e_),w(w_)
{
};
long long to,e,w;
};
long long c[200005];
std::vector<node>edge[200005];
long long father[200005][40],depth[200005];
void dfs(long long x,long long fa)
{
father[x][0]=fa;
depth[x]=depth[fa]+1;
for(long long i=0; i<edge[x].size(); i++)
{
if(edge[x][i].to!=fa)
{
dfs(edge[x][i].to,x);
}
}
for(long long i=1; (1<<i)<=depth[x]; i++)
{
father[x][i]=father[father[x][i-1]][i-1];
}
}
long long lca(long long x,long long y)
{
if(depth[x]<depth[y])
{
std::swap(x,y);
}
for(long long i=35; i>=0; i--)
{
if(depth[father[x][i]]>=depth[y])
{
x=father[x][i];
}
if(x==y)
{
return x;
}
}
for(long long i=35; i>=0; i--)
{
if(father[x][i]!=father[y][i])
{
x=father[x][i];
y=father[y][i];
}
}
return father[x][0];
}
long long ans=0;
void query(long long x)
{
long long fa=0;
for(long long i=0; i<edge[x].size(); i++)
{
if(edge[x][i].to!=father[x][0])
{
query(edge[x][i].to);
c[x]+=c[edge[x][i].to];
}
else
{
fa=i;
}
}
ans+=std::min(edge[x][fa].e*c[x],edge[x][fa].w);
}
int main()
{
long long n;
std::cin>>n;
for(long long i=1; i<n; i++)
{
long long u,v,e,w;
std::cin>>u>>v>>e>>w;
edge[u].push_back(node(v,e,w));
edge[v].push_back(node(u,e,w));
}
dfs(1,0);
for(long long i=2; i<=n; i++)
{
long long l=lca(i-1,i);
c[l]-=2;
c[i-1]++;
c[i]++;
}
query(1);
std::cout<<ans<<std::endl;
}
谢谢qwq