https://www.luogu.org/problemnew/show/P1131

分析

我们设t[i]为以i为根的子树中需要最久达到的点所需的时间

那么我们容易用一次DFS预处理出来，再DFS记录深入到当前点已经加过k次，ans=Σ(t[rt]-t[u]-k),k=t[rt]-t[u]

 

#include 
      
       #include 
       
        using namespace std;const int N=5e5+10;struct Graph {    int v,nx,w;}g[2*N];int cnt,list[N];int n,rt;int tme[N],mx;long long ans;void Add(int u,int v,int w) {    g[++cnt]=(Graph){v,list[u],w};list[u]=cnt;    g[++cnt]=(Graph){u,list[v],w};list[v]=cnt;}void DFS(int u,int fa) {    for (int i=list[u];i;i=g[i].nx)        if (g[i].v!=fa) {            tme[g[i].v]=tme[u]+g[i].w;            DFS(g[i].v,u);        }    for (int i=list[u];i;i=g[i].nx)        if (g[i].v!=fa) tme[u]=max(tme[u],tme[g[i].v]);}void DFS(int u,int fa,int t) {    for (int i=list[u];i;i=g[i].nx)        if (g[i].v!=fa) {            ans+=mx-tme[g[i].v]-t;            DFS(g[i].v,u,mx-tme[g[i].v]);        }}int main() {    scanf("%d%d",&n,&rt);    for (int i=1,u,v,w;i