codeforces 293 E--點分治+樹狀數組

来源:http://www.cnblogs.com/gjghfd/archive/2017/02/17/6409441.html
-Advertisement-
Play Games

題目大意: 給出一棵樹,每條邊有權值,求經過少於l條邊,權值和少於w的路徑總數。 點分治。每次求出所有點到重心的距離,按w排序,然後維護一個樹狀數組,記錄經過的邊<=i的點個數。由於可能兩個點都在一棵子樹中,再容斥一下就好了。 代碼: 1 #include<iostream> 2 #include< ...


題目大意:

給出一棵樹,每條邊有權值,求經過少於l條邊,權值和少於w的路徑總數。

 

點分治。每次求出所有點到重心的距離,按w排序,然後維護一個樹狀數組,記錄經過的邊<=i的點個數。由於可能兩個點都在一棵子樹中,再容斥一下就好了。

代碼:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 inline char nc(){
 7   static char buf[100000],*p1=buf,*p2=buf;
 8   if(p1==p2){
 9     p2=(p1=buf)+fread(buf,1,100000,stdin);
10     if(p1==p2)return EOF;
11   }
12   return *p1++;
13 }
14 inline void Read(int& x){
15   char c=nc();
16   for(;c<'0'||c>'9';)c=nc();
17   for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
18 }
19 #define N 100001
20 #define lowbit(x) x&-x
21 #define ll long long
22 struct Edge{
23   int t,nx,w;
24 }e[N<<1];
25 struct Node{
26   int d,w;
27 }a[N];
28 int i,j,k,n,m,h[N],f[N],L,w,Son[N],Sum,Num,x,y,t,c[N],Rt,l,r,M;
29 bool b[N];
30 ll Ans;
31 inline void Add(int x,int y,int z){
32   e[++Num].t=y;e[Num].w=z;e[Num].nx=h[x];h[x]=Num;
33 }
34 inline int _Max(int x,int y){return x>y?x:y;}
35 inline int _Min(int x,int y){return x>y?y:x;}
36 inline bool Cmp(Node a,Node b){return a.w<b.w;}
37 inline void Update(int x,int y){if(x==0)return;for(;x<=M;x+=lowbit(x))c[x]+=y;}
38 inline int Query(int x){int Ans=0;for(;x>0;x-=lowbit(x))Ans+=c[x];return Ans;}
39 inline void Get_root(int x,int F){
40   f[x]=0;Son[x]=1;
41   for(int i=h[x];i;i=e[i].nx){
42     int v=e[i].t;
43     if(e[i].t==F||b[e[i].t])continue;
44     Get_root(e[i].t,x);Son[x]+=Son[e[i].t];
45     f[x]=_Max(f[x],Son[e[i].t]);
46   }
47   f[x]=_Max(f[x],Sum-Son[x]);
48   if(f[x]<f[Rt])Rt=x;
49 }
50 inline void Dfs(int x,int F,int y,int z){
51   if(F!=0){a[++t].d=y;a[t].w=z;M=_Max(M,y);}
52   for(int i=h[x];i;i=e[i].nx){
53     int v=e[i].t;
54     if(v==F||b[v])continue;
55     Dfs(v,x,y+1,z+e[i].w);
56   }
57 }
58 inline ll Calc(int x,int y,int z,bool Flag){
59   t=M=0;if(Flag)Dfs(x,0,y,z);else Dfs(x,-1,y,z);
60   sort(a+1,a+t+1,Cmp);
61   l=1;r=t;ll Ans=0;
62   for(int i=1;i<=M;i++)c[i]=0;
63   for(int i=l;i<=r;i++)Update(a[i].d,1);
64   if(Flag)for(int i=l;i<=r;i++)if(a[i].w<=w&&a[i].d<=L)Ans++;
65   while(l<r)
66   if(a[l].w+a[r].w<=w){
67     Update(a[l].d,-1);
68     Ans+=Query(_Min(L-a[l++].d,M));
69   }else Update(a[r--].d,-1);
70   return Ans;
71 }
72 inline void Solve(int x){
73   b[x]=1;
74   Ans+=Calc(x,0,0,1);
75   for(int i=h[x];i;i=e[i].nx){
76     int v=e[i].t;
77     if(b[v])continue;
78     Ans-=Calc(v,1,e[i].w,0);
79     f[Rt=0]=n+1;Sum=Son[v];Get_root(v,0);
80     Solve(Rt);
81   }
82 }
83 int main()
84 {
85   Read(n);Read(L);Read(w);
86   for(i=1;i<n;i++){
87     Read(x);Read(y);
88     Add(i+1,x,y);
89     Add(x,i+1,y);
90   }
91   f[Rt=0]=n+1;Sum=n;Get_root(1,0);
92   Solve(Rt);
93   printf("%I64d",Ans);
94   return 0;
95 }
codeforces293E

 


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

-Advertisement-
Play Games
更多相關文章
  • 本文為作者原創,轉載請註明出處,謝謝. 本文適用於mybatis框架初學者,可以通過這個小例子,初識mybatis的簡單易用. 1.創建工程,導入jar包 創建一個java工程或者web工程都可以,然後導入mybatis的jar包和依賴包還有資料庫的jar包,本人使用Oracle10g資料庫 myb ...
  • 在使用“PHPWAMP自動任務”時,不少學生遇到如下問題: “phpwamp綠色集成環境重啟動電腦(伺服器)後,不會自動啟動網站服務” (如果是其他環境或是自己搭建時遇到此問題,也是可以用此法解決) 此文章內容符合: 為什麼網站服務由手動變成自動後還是無法重啟? 為什麼我把服務設置成自動後,開機又變 ...
  • 本文地址 分享提綱: 1.概述 2.安裝 3.編寫第一個測試用例 4.PHPUnit高級 5.參考 分享提綱: 1.概述 2.安裝 3.編寫第一個測試用例 4.PHPUnit高級 5.參考 1.概述 1)【測試框架】 它是一款輕量級的PHP測試框架,是一個xUnit的體繫結構的單元測試框架。複雜的項 ...
  • 本試題共40道選擇題,10道判斷題,考試時間1個半小時 一:選擇題(單項選擇,每題2分): 1. LAMP具體結構不包含下麵哪種(A ) A:Windows系統 B:Apache伺服器 C:MySQL資料庫 D:PHP語言 2. 以下哪個SQL語句是正確的(D) A:insert into user ...
  • 1. LAMP具體結構不包含下麵哪種(A ) A:Windows系統 如果是這個就是WMP B:Apache伺服器 C:MySQL資料庫 D:PHP語言 2. 以下哪個SQL語句是正確的(D ) A:insert into users 少了一個values (‘p001’,’張三’,’男’); B: ...
  • 轉載請標明出處: "http://www.cnblogs.com/why168888/p/6407980.html" 本文出自: "【Edwin博客園】" Python迭代 1. 什麼是迭代 註意: 集合是指包含一組元素的數據結構,我們已經介紹的包括: 1. 有序集合:list,tuple,str和 ...
  • 安全問題已經成為一個越來越重要的問題,在Java中如何對重要數據進行加密解密是本文的主要內容。 一、常用的加密/解密演算法 1.Base64 嚴格來說Base64並不是一種加密/解密演算法,而是一種編碼方式。Base64不生成密鑰,通過Base64編碼後的密文就可以直接“翻譯”為明文,但是可以通過向明文 ...
  • 一、myeclipse之web項目的部署(發佈)流程 web項目的部署(發佈)流程2008-01-18 14:35 在myeclipse下新建web工程abc。系統設置預設如下: 項目保存位置:workspace目錄\abc Source文件夾:src,保存所有的Java類文件(.java文件)和x ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...