BZOJ1468: Tree

来源:https://www.cnblogs.com/zwfymqz/archive/2017/12/26/8120176.html
-Advertisement-
Play Games

Description 給你一棵TREE,以及這棵樹上邊的距離.問有多少對點它們兩者間的距離小於等於K Input N(n<=40000) 接下來n-1行邊描述管道,按照題目中寫的輸入 接下來是k Output 一行,有多少對點之間的距離小於等於k Sample Input 7 1 6 13 6 3 ...


Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1736  Solved: 961
[Submit][Status][Discuss]

Description

給你一棵TREE,以及這棵樹上邊的距離.問有多少對點它們兩者間的距離小於等於K

Input

N(n<=40000) 接下來n-1行邊描述管道,按照題目中寫的輸入 接下來是k

Output

一行,有多少對點之間的距離小於等於k

Sample Input

7
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
10

Sample Output

5

HINT

 

Source

LTC男人八題系列

[Submit][Status][Discuss]


HOME Back

 

 

點分治,真是個神奇的東西。

對於這個題而言,求出所有的距離,再利用雙指針法統計答案

具體來說就是記錄兩個變數,當統計出一個點到其他點的距離時

如果到$l$+到$r$的距離是滿足條件的,那麼$l-r$中間的點就都滿足條件

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
const int INF=1e7+10;
inline char nc()
{   
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
    return x*f;
}
struct node
{
    int u,v,w,nxt; 
}edge[MAXN];
int head[MAXN];
int num=1;
inline void AddEdge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].w=z;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int K,F[MAXN],siz[MAXN],root,sum,vis[MAXN],tot[MAXN],cnt,deep[MAXN],ans=0;
void GetRoot(int now,int fa)
{
    siz[now]=1;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(edge[i].v==fa||vis[edge[i].v]) continue;
        GetRoot(edge[i].v,now);
        siz[now]+=siz[edge[i].v];
        F[now]=max(F[now],siz[edge[i].v]);
    }
    F[now]=max(F[now],sum-siz[now]);
    if(F[now]<F[root]) root=now;
}
void GetDeep(int now,int fa)
{
    tot[++cnt]=deep[now];
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(vis[edge[i].v]||edge[i].v==fa) continue;
        deep[edge[i].v]=deep[now]+edge[i].w;
        GetDeep(edge[i].v,now);
    }
}
int Calc(int now,int val)//now點滿足條件的個數 
{
    cnt=0;deep[now]=val;//一個小技巧 
    GetDeep(now,0);
    sort(tot+1,tot+cnt+1);
    int l=1,r=cnt,NowAns=0;
    while(l<r)
    {
        if(tot[l]+tot[r]<=K) NowAns+=r-l,l++;
        else r--;
    }
    return NowAns;
}
void Solve(int now)
{
    vis[now]=1;//別忘了打標記 
    ans+=Calc(now,0);
    
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(vis[edge[i].v]) continue;
        ans-=Calc(edge[i].v,edge[i].w);
        sum=siz[edge[i].v];
        root=0;
        GetRoot(edge[i].v,0);
        Solve(edge[i].v);
    }
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    memset(head,-1,sizeof(head));
    int N=read();
    for(int i=1;i<=N-1;i++)
    {
        int x=read(),y=read(),z=read();
        AddEdge(x,y,z);
        AddEdge(y,x,z);
    }
    K=read();
    F[0]=INF;sum=N;
    //這裡有個技巧,把root設置為0,f[0]=INF,那麼可以解決找重心時的邊界問題 
    GetRoot(1,0);
    Solve(root);
    printf("%d",ans);
    return 0;
}

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • ##補充:列表生成器 1 #兩個理解例子 2 a=[x**2 for x in range(10)] #取x,然後執行x**2,在存放到列表裡面 3 print(a) #[0,1,4,9,16,25,36,49,64,81] 4 5 def f(n): 6 return n**2 7 a=[f(x) ...
  • 1 package demo; 2 3 import java.sql.Connection; 4 import java.sql.DriverManager; 5 import java.sql.PreparedStatement; 6 import java.sql.SQLException; ... ...
  • 反射 一.獲得Class文件對象的三種方式(返回值都是Class類的對象) 1.通過類名調用class()獲得。 格式:類名.class(); 2.通過對象調用getClass()方法獲得; 格式:對象名.getClass(); 3.通過Class類的靜態方法forName()獲得 格式:Class ...
  • c3p0-0.9.2.1 jar包和mchange-commons-java-0.2.3.4 jar 包 下載地址: https://pan.baidu.com/s/1jHDiR7g 密碼 tyek ...
  • 環境:python3.6 目的:根據列表 中的字元串導入對應模塊 僅筆記,並知道有什麼實際用處 ...
  • ##閉包 :內部函數,在外部調用不在他函數範圍的變數 def outer(): x=10 def inner(): print(x) return inner #outer()() f=outer() f() 這裡inner就是一個閉包,閉包=內部函數+環境,這裡環境是x=10。閉包是為瞭解釋調用不 ...
  • node-schedule每次都是通過新建一個scheduleJob對象來執行具體方法。 時間數值按下表表示 指定時間有兩種方式1 字元串指定 *之間一定要加空格,否則不執行 每到秒數為4的倍數時執行 在秒位*後加/4 和後面的*之間要有空格schedule.scheduleJob('*/4 * * ...
  • Infi-chu: http://www.cnblogs.com/Infi-chu/ 模塊:filecmp 安裝:Python版本大於等於2.3預設自帶 功能:實現文件、目錄、遍歷子目錄的差異 常用方法: 1.單文件對比(cmp): 2.多文件對比(cmpfiles): 3.目錄對比(dircmp) ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...