2 条题解

  • 0
    @ 2025-12-31 13:10:17
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 4e4 + 4, Q = 2e4 + 7;
    vector< pair<int, int> > G[N];
    int n, L;ll ans;
    int siz[N], all, rt, rtmaxsiz;
    int dis[N], cnt;
    bool del[N];
    
    void getroot(int x, int xfa)
    {
        siz[x] = 1;
        int xmaxsiz = 0;
        for (auto i:G[x])
            if (i.first != xfa && !del[i.first]){
                getroot(i.first, x);
                siz[x] += siz[i.first];
                xmaxsiz = max(xmaxsiz, siz[i.first]);
            }
        xmaxsiz = max(xmaxsiz, all - siz[x]);
        if (xmaxsiz < rtmaxsiz) rtmaxsiz = xmaxsiz, rt = x;
    }
    
    void getdis(int x, int xfa, int w)
    {
        if(w>L) return ;
        dis[++cnt] = w ;
        for (auto i:G[x])
            if (i.first != xfa && !del[i.first])
                getdis(i.first, x, w + i.second);
    }
    
    ll calc(int x,int w)
    {
        cnt = 0;
        getdis(x, 0, w);
        sort(dis + 1, dis + cnt + 1);
        int l = 1, r = cnt;
        ll res = 0;
        while (l < r)
        {
            if (dis[l] + dis[r] <= L)
                res += r - l, l++;
            else
                r--;
        }
        return res;
    }
    
    void divide(int x)
    {
        ans+=calc(x,0);
        del[x] = true;
        for (auto i:G[x])
            if (!del[i.first]){
                ans-=calc(i.first,i.second);
                all=rtmaxsiz=siz[i.first];getroot(i.first, 0);getroot(rt, x);
                divide(rt);
            }
    }
    
    int main()
    {
        ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
        cin >> n ;
        for (int i = 2, x, y, w; i <= n; i++)
        {
            cin >> x >> y >> w;
            G[x].push_back({y, w});
            G[y].push_back({x, w});
        }
        cin >> L;
        ans = 0;
    
        all=rtmaxsiz=n;getroot(1, 0);getroot(rt, 0);
        divide(rt);
    
        cout << ans << "\n";
        return 0;
    }
    
    • -1
      @ 2025-12-31 12:38:54
      #include<bits/stdc++.h>
      using namespace std;
      #define fi first
      #define se second
      #define pb push_back
      const int N=4e4+10;
      int n,k,rt,cnt,mg,all,ans;
      int sz[N],d[N];bool v[N];
      vector<pair<int,int> >e[N];
      void getg(int x,int xfa)
      {
      	int g=0;sz[x]=1;
      	for(auto i:e[x])
      	{
      		int y=i.fi;
      		if(v[y]||y==xfa)continue;
      		getg(y,x);
      		sz[x]+=sz[y];
      		g=max(g,sz[y]);
      	}
      	g=max(g,all-sz[x]);
      	if(g<mg)mg=g,rt=x;
      }
      void getd(int x,int xfa,int dis)
      {
      	if(dis>k)return;
      	d[++cnt]=dis;
      	for(auto i:e[x])
      	{
      		int y=i.fi,w=i.se;
      		if(v[y]||y==xfa)continue;
      		getd(y,x,w+dis);
      	}
      }
      int calc(int x,int dis)
      {
      	cnt=0;getd(x,0,dis);
      	sort(d+1,d+cnt+1);
      	int l=1,r=cnt,res=0;
      	while(l<r)
      	{
      		if(d[l]+d[r]<=k)
      			res+=r-l,l++;
      		else r--;
      	}
      	return res;
      }
      void solve(int x)
      {
      	v[x]=1;ans+=calc(x,0);
      	for(auto i:e[x])
      	{
      		int y=i.fi,w=i.se;
      		if(v[y])continue;
      		ans-=calc(y,w);
      		mg=all=sz[y];
      		getg(y,0);
      		getg(rt,x);
      		solve(rt);
      	}
      }
      int main()
      {
      	scanf("%d",&n);
      	for(int i=1,x,y,w;i<n;i++)
      	{
      		scanf("%d%d%d",&x,&y,&w);
      		e[x].pb({y,w});
      		e[y].pb({x,w});
      	}
      	scanf("%d",&k);
      	all=rt=n;
      	getg(1,0);
      	solve(rt);
      	printf("%d\n",ans);
      	return 0;
      }
      
      • 1

      信息

      ID
      3121
      时间
      200ms
      内存
      512MiB
      难度
      7
      标签
      递交数
      61
      已通过
      16
      上传者