NOIP 道路建设-树型DP

洛谷传送门：https://www.luogu.com.cn/problem/P2052

分析：本题算是一道比较初级的树型DP了，可数据范围过大，用深搜会爆栈，所以替换为宽搜

宽搜实现树型DP的原理是当一次搜索完成之后，队列中的元素（ 1~N）即为搜索顺序，只需在搜索过程中记录父子关系，便可在搜索之后完成树型DP

通过树型DP后我们可维护出每个点的子树大小，所以显然答案即为

ans+=abs(n-2*s[x])*val

注意：在搜索后的DP中应从队尾至队首遍历，且因为本题读入数据过大，需要写读入优化（感谢fsw大佬提供的读入优化qwq）且ans爆int

代码如下

#include<stdio.h>
#include<cstring>
#define N 1000001
int n;
int head[N],nxt[2*N],to[2*N],v[2*N];
int tot=0;
int Q[N];
long long val[N];
bool vis[N];
int l,r;
int F[N];
long long s[N];
int abs(int x)
{
return x>0?x:-x; 
}
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
    int x=0,f=1;
    char ch=nc();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=nc();
    }
    while(ch>='0'&&ch<='9')
        x=x*10+ch-'0',ch=nc();
    return x*f;
}
void bfs(int p)
{
    int l=0,r=0;
    Q[r++]=p;vis[p]=1;
        while(l<r)
        {
            p=Q[l++];
            for(int i=head[p];i;i=nxt[i])
            {
                if(!vis[to[i]])
                {
                    F[to[i]]=p;
                    val[to[i]]=v[i];
                    Q[r++]=to[i];
                    vis[to[i]]=1;
                }
            }
        }
}
void add(int x,int y,int z)
{
    v[++tot]=z;
    to[tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;    
}
int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        x=read();y=read();z=read();
        add(x,y,z);      
        add(y,x,z);
    }
    bfs(1);
    long long ans=0;
    for(int i=n-1;i>=0;i--)
    {
  
        s[Q[i]]++;
        s[F[Q[i]]]+=s[Q[i]];
        ans+=abs(n-2*s[Q[i]])*val[Q[i]];
    //  printf("%d %d",Q[i],s[Q[i]]);
    //  printf(" ans=%d
",ans);
    }
    printf("%lld",ans);