头像

洛零


访客:1244

离线:9小时前


活动打卡代码 AcWing 503. 借教室

洛零
9小时前
#include <iostream>
#include <cstring>

using namespace std;

const int N=1e6+5;
int n,m;
int a[N],h[N];
int d[N],s[N],t[N];

bool check(int x) {
    memset(a,0,sizeof(a));
    for(int i=1;i<=x;i++) {
        a[s[i]]+=d[i];
        a[t[i]+1]-=d[i];
    }
    for(int i=1;i<=n;i++)
      a[i]+=a[i-1];
    for(int i=1;i<=n;i++) {
        if(a[i]>h[i])
          return false;
    }
    return true;
}

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
      cin>>h[i];
    for(int i=1;i<=m;i++)
      cin>>d[i]>>s[i]>>t[i];
    int l=0,r=m,ans; 
    while(l<r) {
        int mid=(l+r+1)>>1;
        if(check(mid))
          l=mid;
        else
          r=mid-1,ans=mid;
    }
    if(l==m) {
        cout<<0;
        return 0;
    }
    cout<<-1<<endl;
    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 344. 观光之旅

洛零
1天前
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
const int N=3e2+5,INF=0x3f3f3f3f;
int n,m;
int a[N][N],d[N][N],p[N][N];
int ans=INF;
vector<int> v;

void get(int x,int y) {
    if(p[x][y]==0)
      return ;
    get(x,p[x][y]);
    v.push_back(p[x][y]);
    get(p[x][y],y);
}

int main() {
    cin>>n>>m;
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=n;i++)
      a[i][i]=0;
    while(m--) {
        int u,v,w;
        cin>>u>>v>>w;
        a[u][v]=min(a[u][v],w);
        a[v][u]=min(a[v][u],w);
    }
    memcpy(d,a,sizeof(a));
    for(int k=1;k<=n;k++) {
        for(int i=1;i<k;i++)
          for(int j=i+1;j<k;j++)
            if((long long)d[i][j]+a[j][k]+a[k][i]<ans) {
                ans=d[i][j]+a[j][k]+a[k][i];
                v.clear();
                v.push_back(i);
                get(i,j);
                v.push_back(j);
                v.push_back(k);
            }
        for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
            if(d[i][j]>d[i][k]+d[k][j]) {
                d[i][j]=d[i][k]+d[k][j];
                p[i][j]=k;
            }
    }
    if(ans==INF) {
        cout<<"No solution.";
        return 0;
    }
    for(int i=0;i<v.size();i++)
      cout<<v[i]<<' ';
    return 0;
}




洛零
4天前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N=1e4+5,M=2e5+5,INF=1e9; 
int n,m,s,t;
int head[N],to[M],nxt[M],val[M],cnt;
int d[N],cur[N],maxflow;
bool vis_s[N],vis_t[N];

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

bool bfs() {
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        cur[u]=head[u];
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i],w=val[i];
            if(w>0 and !d[v]) {
                q.push(v);
                d[v]=d[u]+1;
                if(v==t)
                  return true;
            }
        }
    }
    return false;
}

int dfs(int u,int lim) {
    if(u==t)
      return lim;
    int flow=0;
    for(int i=cur[u];i and flow<lim;i=nxt[i]) {
        int v=to[i],w=val[i];
        cur[u]=i;
        if(d[v]==d[u]+1 and w>0) {
            int k=dfs(v,min(lim-flow,w));
            if(!k)
              d[v]=-1;
            val[i]-=k;
            val[i^1]+=k;
            flow+=k; 
        }
    }
    return flow;
}

void dfs_s(int u) {
    vis_s[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        if(val[i]>0 and !vis_s[to[i]])
          dfs_s(to[i]);
    }
}

void dfs_t(int u) {
    vis_t[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        if(val[i^1]>0 and !vis_t[to[i]])
          dfs_t(to[i]);
    }
}

int main() {
    cnt=1;
    cin>>n>>m;
    s=0,t=n-1;
    for(int i=1;i<=m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    int flow;
    while(bfs())
      while(flow=dfs(s,INF))
        maxflow+=flow;
    dfs_s(s);
    dfs_t(t);
    int ans=0;
    for(int i=2;i<=m*2+1;i+=2)
      if(!val[i] and vis_t[to[i]] and vis_s[to[i^1]])
        ans++;
    cout<<ans;
    return 0;
}



活动打卡代码 AcWing 2179. 圆桌问题

洛零
5天前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N=1e5+5,M=2e5+5,INF=1e9;
int n,m,s,t;
int r[N],c[N],sum;
int head[N],to[M],nxt[M],val[M],cnt; 
int d[N],cur[N],maxflow;

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

bool bfs() {
    memset(d,0,sizeof(d));
    d[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        cur[u]=head[u];
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i],w=val[i];
            if(!d[v] and w>0) {
                d[v]=d[u]+1;
                q.push(v);
                if(v==t)
                  return true;
            }
        }
    }
    return false;
}

int dfs(int u,int lim) {
    if(u==t)
      return lim;
    int flow=0;
    for(int i=cur[u];i and flow<lim;i=nxt[i]) {
        int v=to[i],w=val[i];
        cur[u]=i;
        if(d[v]==d[u]+1 and w>0) {
            int k=dfs(v,min(lim-flow,w));
            if(!k)
              d[v]=-1;
            val[i]-=k;
            val[i^1]+=k;
            flow+=k;
        }
    }
    return flow;
}

int main() {
    cnt=1;
    cin>>m>>n;
    s=0;t=m+n+1;
    for(int i=1;i<=m;i++) {
        cin>>r[i];
        sum+=r[i];
        add(s,i,r[i]);
        add(i,s,0);
    }
    for(int i=1;i<=n;i++) {
        cin>>c[i];
        add(i+m,t,c[i]);
        add(t,i+m,0);
    }
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            add(i,j+m,1);
            add(j+m,i,0);
        }
    }


    int flow;
    while(bfs())
      while(flow=dfs(s,INF))
        maxflow+=flow;
    if(maxflow!=sum) {
        cout<<0;
        return 0;
    }
    cout<<1<<endl;
    for(int u=1;u<=m;u++) {
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i];
            if(v>m and val[i]==0)
              cout<<v-m<<' ';
        }
        cout<<endl;
    }
    return 0;
}



洛零
6天前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N=1e2+5,M=6e3+5,INF=1e9;
int n,m,s,t;
int head[N],to[M],nxt[M],val[M],cnt;
int d[N],cur[N],maxflow;

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

bool bfs() {
    memset(d,0,sizeof(d));
    d[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        cur[u]=head[u];
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i],w=val[i];
            if(!d[v] and w>0) {
                d[v]=d[u]+1;
                q.push(v);
                if(v==t)
                  return true;
            }
        } 
    }
    return false;
}

int dfs(int u,int lim) {
    if(u==t)
      return lim;
    int flow=0;
    for(int i=cur[u];i and flow<lim;i=nxt[i]) {
        int v=to[i],w=val[i];
        cur[u]=i;
        if(d[v]==d[u]+1 and w>0) {
            int k=dfs(v,min(lim-flow,w));
            if(!k)
              d[v]=-1;
            val[i]-=k;
            val[i^1]+=k;
            flow+=k;
        }
    }
    return flow;
}

int main() {
    cnt=1;
    cin>>n>>m;
    s=0;t=m+1;
    int u=0,v=0;
    for(int i=1;i<=n;i++) {
        add(s,i,1);
        add(i,s,0);
    }
    for(int i=n+1;i<=m;i++) {
        add(i,t,1);
        add(t,i,0);
    }
    while(cin>>u>>v,u!=-1) {
        add(u,v,1);
        add(v,u,0);
    }
    int flow;
    while(bfs())
      while(flow=dfs(s,INF)) 
        maxflow+=flow;
    cout<<maxflow<<endl;
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=nxt[j]) {
            if(val[j]==0 and to[j]>=n+1 and to[j]<=m) {
                cout<<i<<' '<<to[j]<<endl;
                break;
            }
        }
    }
    return 0;
}




洛零
6天前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N=1e4+5,M=2e5+5,INF=1e9; 
int n,m,s,t;
int head[N],to[M],nxt[M],val[M],cnt;
int d[N],cur[N],maxflow;

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

bool bfs() {
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        cur[u]=head[u];
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i],w=val[i];
            if(w>0 and !d[v]) {
                q.push(v);
                d[v]=d[u]+1;
                if(v==t)
                  return true;
            }
        }
    }
    return false;
}

int dfs(int u,int lim) {
    if(u==t)
      return lim;
    int flow=0;
    for(int i=cur[u];i and flow<lim;i=nxt[i]) {
        int v=to[i],w=val[i];
        cur[u]=i;
        if(d[v]==d[u]+1 and w>0) {
            int k=dfs(v,min(lim-flow,w));
            if(!k)
              d[v]=-1;
            val[i]-=k;
            val[i^1]+=k;
            flow+=k; 
        }
    }
    return flow;
}

int main() {
    cnt=1;
    cin>>n>>m>>s>>t;
    while(m--) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    int flow;
    while(bfs())
      while(flow=dfs(s,INF))
        maxflow+=flow;
    cout<<maxflow;
    return 0;
}




洛零
6天前

首先,如果一个流的残量网络里面没有可行流,那么这个流就是最大流。
EK算法就是基于这个事实的算法,时间复杂度为$O(nm^2)$(n为点数m为边数)。
详细地讲,过程如下:
- 1、找增广路
- 2、更新残量网络增广路上的流量
- 3、重复执行1、2直到网络里没有增广路

对于边与反向边的话,我们使用“成对存储”的技巧来存,这样访问反向边就很方便了。
然后找增广路的过程中需要记录经过的边,以便于之后更新。
请注意cnt初值为1,极其容易写错。

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N=1e3+5,M=2e4+5,INF=1e9;  //因为我们维护残留网络,所以要建反向边,边数*2
int n,m,s,t;    //点数,边数,源点,汇点
int head[N],to[M],nxt[M],val[M],cnt;    //链式前向星
int pre[N],inc[N],maxflow;  
//pre[i]表示bfs里,到点i的边的编号
//inc表示源点到当前点的流量
//maxflow即最大流
bool vis[N];    //记录点有没有被访问过

void add(int u,int v,int w) {   //链式前向星加边
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

bool bfs() {    //找一条增广路
    memset(vis,0,sizeof(vis));  //清空vis数组
    queue<int> q;   //bfs的队列
    q.push(s);
    inc[s]=INF; //源点的流量即无穷大
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i],w=val[i];
            if(w>0 and !vis[v]) {   //边权大于0(即增广路)
                inc[v]=min(inc[u],w);   //流量为边权与inc[u]的最小值(可以理解为一部分水流被这条管道挡住了)
                q.push(v);
                vis[v]=true;
                pre[v]=i;   //记录前向边
                if(v==t)    //有增广路了
                  return true;
            }
        }
    }
    return false;   //找不到增广路
}

void update() {
    int p=t;    //由于我们是反向存边,所以说需要从汇点往源点走
    while(p!=s) {
        val[pre[p]]-=inc[t];    //残量网络的定义
        val[pre[p]^1]+=inc[t];  //i^1即i的反向边
        p=to[pre[p]^1]; //往前走
    }
    maxflow+=inc[t];    //最大流加上当前增广路到汇点的流量
}

int main() {
    cnt=1;  //重要!网络流里面的所有cnt都从1开始,来成对存储!
    cin>>n>>m>>s>>t;
    while(m--) {
        int u,v,w;
        cin>>u>>v>>w;
        //直接建立残量网络
        add(u,v,w);
        add(v,u,0);
    }
    //EK算法的核心
    while(bfs())    //一直找增广路
      update(); //更新权值,并增加最大流
    cout<<maxflow;  //输出最大流
    return 0;
}


活动打卡代码 AcWing 2171. EK求最大流

洛零
7天前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N=1e3+5,M=2e4+5,INF=1e9; 
int n,m,s,t;
int head[N],to[M],nxt[M],val[M],cnt;
int pre[N],inc[N],maxflow;
bool vis[N];

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

bool bfs() {
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    inc[s]=INF;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i],w=val[i];
            if(w>0 and !vis[v]) {
                inc[v]=min(inc[u],w);
                q.push(v);
                vis[v]=true;
                pre[v]=i;
                if(v==t)
                  return true;
            }
        }
    }
    return false;
}

void update() {
    int p=t;
    while(p!=s) {
        val[pre[p]]-=inc[t];
        val[pre[p]^1]+=inc[t];
        p=to[pre[p]^1];
    }
    maxflow+=inc[t];
}

int main() {
    cnt=1;
    cin>>n>>m>>s>>t;
    while(m--) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    while(bfs())
      update();
    cout<<maxflow;
    return 0;
}



活动打卡代码 AcWing 311. 月之谜

洛零
8天前
#include <cstdio>
#include <cstring>

using namespace std;
typedef unsigned long long ll;
const int N=202;
ll l,r;
ll a[21],f[21][N][N];
ll sum;

ll dp(int eq,int dep,int cur,int mod) {
    if(cur>sum)
      return 0;
    if(!dep)
      return (mod==0 and cur==sum);
    if((!eq) and (~f[dep][cur][mod]))
      return f[dep][cur][mod];
    int ed=(eq)?a[dep]:9;
    ll ret=0;
    for(int i=0;i<=ed;i++)
      ret+=dp(eq and (i==ed),dep-1,cur+i,(mod*10+i)%sum);
    if(!eq)
      f[dep][cur][mod]=ret;
    return ret;  
}

ll work(ll n) {
    a[0]=0;
    for(;n;n/=10)
      a[++a[0]]=n%10;
    ll ret=0;
    for(int i=1;i<=a[0]*9;i++) {
        sum=i;
        memset(f,-1,sizeof(f));
        ret+=dp(1,a[0],0,0);
    }
    return ret;
}

int main() {
    scanf("%llu%llu",&l,&r);
    printf("%llu",work(r)-work(l-1));
    return 0;
}



分享 树形dp

洛零
10天前

前言

树形dp是一种在树上做的dp,通常的结构为:

void dp(int u) {
    v[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        dfs(v);
        update(f[u],f[v]);  //用f[v]来更新f[u]
    }
}

先递归子节点,再从子节点向上转移,这样就是一般的树形dp。

树直径

考虑这样一道题:
给定一棵无根树,求两个距离最远的节点间的距离,两个相邻结点距离为1。
首先,两个距离最远的结点必定是“边界点”,即度为1的点。
我们不妨对于每个点,求出这个点到这个点的子树的所有边界点的最长距离与次长距离,设为f[x][1],f[x][2],那么答案也就自然是$\max_{1\leq i\leq n}(f[i][1]+f[i][2])$
主要的瓶颈就在于:如何求出每个点的f呢?
我们看下dp代码

void dfs(int u) {
    v[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int y=to[i];
        if(v[y])    //已经访问过了(即父节点),跳过
          continue;
        dfs(y); //递归子节点
        //以下代码请好好斟酌
        if(h[u][1]<=h[y][1]+1) {    //如果最长路可以更新
            h[u][2]=h[u][1];    //将次长路更新为最长路
            h[u][1]=h[y][1]+1;  //将最长路更新为新值
        }
        else if(h[u][2]<=h[y][1]+1) //如果次长路可以更新
          h[u][2]=h[y][1]+1;    //更新次长路
    }
}

因为这个树是一个无根树,所以我们从任意一个点开始执行dfs都可以。

树上背包问题

CTSC1997 选课

题目链接:选课acwing286
这n门课构成了一个森林的结构,为了简便,可以添加零号节点为各个树根的父亲,方便dp。
状态定义:f[u][t]表示在以u为根的子树中选t门的最高得分。
状态的转移实际上是一个分组背包模型,一个点的所有子节点看做是一组物品v,每组物品有f[v][i]的价值与i的消费。每组物品中只能取一个。

#include <iostream>
#include <cstring>

using namespace std;
const int N=3e2+5;
int n,m;
int head[N],to[N],nxt[N],cnt;
int score[N];
int f[N][N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}


void dp(int u) {
    f[u][0]=0;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        dp(v);
        for(int t=m;t>=0;t--)   //背包状态转移
          for(int j=t;j>=0;j--)
            f[u][t]=max(f[u][t],f[u][t-j]+f[v][j]);
    }
    if(u!=0)
      for(int i=m;i>0;i--)
        f[u][i]=f[u][i-1]+score[u];
}

int main() {
    memset(f,0xc0,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        int u;
        cin>>u>>score[i];
        add(u,i);
    }
    dp(0);
    cout<<f[0][m];
    return 0;
}

二叉苹果树

题目链接:二叉苹果树
有了上面一道题,这道题就更加简单了,直接看代码。
注意不同的是,这道题是边权,上一题是点权。

#include <iostream>
#include <cstring>

using namespace std;
const int N=3e2+5;
int n,m;
int head[N],to[N],val[N],nxt[N],cnt;
bool vis[N];
int f[N][N];

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void dp(int u) {
    vis[u]=true;
    f[u][0]=0;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i],w=val[i];
        if(vis[v])
          continue;
        dp(v);
        for(int t=m;t>=0;t--)
          for(int j=t;j>=0;j--)
            f[u][t]=max(f[u][t],f[u][t-j-1]+f[v][j]+w); //此处减一是要把自己算上去
    }
}

int main() {
    memset(f,0xc0,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<n;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dp(1);
    cout<<f[1][m];
    return 0;
}

典型树形dp

没有上司的舞会

题目链接:没有上司的舞会acwing285
状态定义:f[u][0]表示当u不选时,u的子树的最大值,f[u][1]表示选u时,u的最大值。
那么很容易写出状态转移方程了。

#include <iostream>
#include <cstdio>

using namespace std;
const int N=2e4+5;
int head[N],nxt[N],to[N],cnt;
int f[N][2],h[N],n,root,in[N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void dp(int p) {
    f[p][0]=0;
    f[p][1]=h[p];
    for(int i=head[p];i;i=nxt[i]) {
        int y=to[i];
        dp(y);  //这边要注意:如果有明确的依赖关系,就不需要判断是否为父亲,建边时建单向边即可。但是如果只是说有一条边,那么就要双向建边,并判断到达点是否为当前点的父亲
        f[p][0]+=max(f[y][1],f[y][0]);  //如果当前点不选,它的下级既可以选也可以不选
        f[p][1]+=f[y][0];   //如果当前点选,那么只有不选它的下级
    }
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>h[i];
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        add(v,u);
        in[u]++;    //记录入度,根的入度必定为0
    }
    for(int i=1;i<=n;i++)
      if(in[i]==0) {
        root=i;
        break;
      }
    dp(root);   //从根开始dp
    cout<<max(f[root][0],f[root][1]);   //选根与不选根取最大值
    return 0;
}

数字转换

题目链接:数字转换
看起来不像树形dp,但我们可以把它转化成数形dp
设一个数x的约数和叫d[x],那么对于每个x我们不妨看做是x到d[x]连一条边。最后求这棵树的直径就行了。

#include <iostream>
#include <cstdio>

using namespace std;
const int N=4e5+5;
int n,m;
int head[N],to[N],nxt[N],cnt;
bool v[N];
int h[N][3],ans;
int sum[N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

//求直径传统艺能
void dfs(int u) {
    v[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int y=to[i];
        if(v[y]) 
          continue;
        dfs(y);
        if(h[u][1]<=h[y][1]+1) {
            h[u][2]=h[u][1];
            h[u][1]=h[y][1]+1;
        }
        else if(h[u][2]<=h[y][1]+1)
          h[u][2]=h[y][1]+1; 
    }
}

int main() {
    cin>>n;
    //求每个数的约数和并加边
    for(int i=1;i<=n;i++) { //枚举因子来求约数和
        if(sum[i]<i) {  //约数和小于原数
            add(i,sum[i]);  //加两条边
            add(sum[i],i);
        }
        for(int j=i*2;j<=n;j+=i)    //枚举i的倍数
          sum[j]+=i;
    }
    dfs(1);
    for(int i=1;i<=n;i++)
      ans=max(ans,h[i][1]+h[i][2]); //直径
    cout<<ans;
    return 0;
}

二次扫描与换根法

如果题目中要对每个点都进行统计,并且这棵树是无根树,那么就可以使用这个方法。
1、第一次扫描,任选一个点为根,执行从下到上的dp
2、第二次扫描,以刚才那个点为根,进行从上到下的推导
我们可以解决比如:求每个点到任意点的最长路,或者次长路等的问题。

Accumulation Degree

这道题目蓝书上面有讲解,就不赘述了。