【BZOJ4543】【POI2014】Hotel加強版(長鏈剖分)

傳送門

題意:求樹上滿足三點之間距離兩兩相等的三元組個數

n≤1e5n\le 1e5n1e5

原題數據是n≤5000n\le5000n5000

考慮怎么做
f[u][i]f[u][i]f[u][i]表示uuu為根,深度為iii的點的個數
g[u][i]g[u][i]g[u][i]表示uuu為根,滿足2點到lcalcalca的距離減去lcalcalcauuu的距離為iii,即dep[x]+dep[y]?3?deplca=idep[x]+dep[y]-3*dep_{lca}=idep[x]+dep[y]?3?deplca?=i的點對個數
換句話說就是還差iii個距離滿足能湊成333元組的點對個數


ans+=g[u][i+1]?f[v][i];ans+=g[u][i+1]*f[v][i];ans+=g[u][i+1]?f[v][i];
ans+=f[u][i?1]?g[v][i];ans+=f[u][i-1]*g[v][i];ans+=f[u][i?1]?g[v][i];
g[u][i+1]+=f[u][i+1]?f[v][i];g[u][i+1]+=f[u][i+1]*f[v][i];g[u][i+1]+=f[u][i+1]?f[v][i];
f[u][i+1]+=f[v][i];f[u][i+1]+=f[v][i];f[u][i+1]+=f[v][i];
g[u][i?1]+=g[v][i];g[u][i-1]+=g[v][i];g[u][i?1]+=g[v][i];

這式子很顯然吧
發現轉移的時候
f[u][i+1]+=f[v][i];f[u][i+1]+=f[v][i];f[u][i+1]+=f[v][i];
g[u][i?1]+=g[v][i];g[u][i-1]+=g[v][i];g[u][i?1]+=g[v][i];
既然只和深度有關,
就可以愉快的長鏈剖分了

復雜度O(n)O(n)O(n)
據說可以點分O(nlogn)O(nlogn)O(nlogn)
關我p事

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<22|1;
#define ll long long
inline char gc(){static char ibuf[RLEN],*ob,*ib;(ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));return (ib==ob)?EOF:*ib++;
}
inline int read(){char ch=gc();int res=0,f=1;while(!isdigit(ch)){if(ch=='-')f=-f;ch=gc();}while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();return res*f;
}
const int N=1000005;
ll *f[N],*g[N],*id,tmp[N<<2],ans;
int n,adj[N],nxt[N<<1],to[N<<1],dep[N],son[N],cnt;
inline void addedge(int u,int v){nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
void dfs1(int u,int fa){for(int e=adj[u];e;e=nxt[e]){int v=to[e];if(v==fa)continue;dfs1(v,u);if(dep[v]>dep[son[u]])son[u]=v;}dep[u]=dep[son[u]]+1;
}
void dfs2(int u,int fa){if(son[u]){f[son[u]]=f[u]+1,g[son[u]]=g[u]-1,dfs2(son[u],u);}f[u][0]=1;ans+=g[u][0];for(int e=adj[u];e;e=nxt[e]){int v=to[e];if(v==fa||v==son[u])continue;f[v]=id,id+=dep[v],g[v]=id+dep[v],id+=dep[v]*2;dfs2(v,u);for(int i=dep[v]-1;~i;i--){ans+=g[u][i+1]*f[v][i];if(i)ans+=f[u][i-1]*g[v][i];g[u][i+1]+=f[u][i+1]*f[v][i];f[u][i+1]+=f[v][i];}for(int i=dep[v]-1;i;i--){g[u][i-1]+=g[v][i];}}
}
int main(){n=read();for(int i=1;i<n;i++){int u=read(),v=read();addedge(u,v),addedge(v,u);}dfs1(1,0);id=tmp;f[1]=id,id+=dep[1],g[1]=id+dep[1],id+=dep[1]*2;dfs2(1,0);cout<<ans;
}

轉載于:https://www.cnblogs.com/stargazer-cyk/p/11145583.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/449359.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/449359.shtml
英文地址,請注明出處:http://en.pswp.cn/news/449359.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

使用vue+webpack從零搭建項目

vue到現在已經成為一個熱門的框架&#xff0c;在項目實踐當中&#xff0c;如果想要創建一個新項目&#xff0c;通常都會使用vue-cli的腳手架工具&#xff0c;毋容置疑能夠方便很多&#xff0c;很多東西也不需要自己親自去配置。都知道&#xff0c;腳手架其實是vue結合webpack去…

CentOS 6 和 CentOS 7 防火墻的關閉

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。CentOS6.5查看防火墻的狀態&#xff1a; 1[linuxidclocalhost ~]$service iptable status顯示結果&#xff1a; 12345[linuxidclocalhost …

怎樣從Linux終端管理進程:10個你必須知道的命令

本文由 極客范 - Ben Zhang 翻譯自 Chris Hoffman。歡迎加入極客翻譯小組&#xff0c;同我們一道翻譯與分享。轉載請參見文章末尾處的要求。Linux終端有一系列有用的命令。它們可以顯示正在運行的進程、殺死進程和改變進程的優先級。本文列舉了一些經典傳統的命令和一些有用新…

易盛極星多合約回測(問題很多)

注意&#xff0c;使用此函數&#xff0c;在考慮手續費時&#xff0c;無法做到統一。 import talib import numpy as np import EsTalib from EsSeries import NumericSeries# 策略參數字典 g_params[p1] 5 g_params[p2] 10 g_params[p3] 120 g_params[ZQ] 5 #交易周期…

Qt 程序獲取程序所在路徑、用戶目錄路徑、臨時文件夾等特殊路徑的方法

Qt 程序獲取程序所在路徑、用戶目錄路徑、臨時文件夾等特殊路徑的方法 經常我們的程序中需要訪問一些特殊的路徑&#xff0c;比如程序所在的路徑、用戶目錄路徑、臨時文件夾等。在 Qt 中實現這幾個功能所用的方法雖然都不難&#xff0c;但是各不相同&#xff0c;每次用到時還要…

搞了個30天學習量化的數據資料,可以bt做全球。數據鏈接白送

待會上傳代碼,資料,打包好了,拿來就能用。累死我了,搞了兩天,必須收費,絕不允許白嫖。不然對不起我熬夜,那么辛苦。 確定后,掃描百度網盤 鏈接:https://pan.baidu.com/s/1C0k6zkjHchFVQaHe4nRMsg?pwd=kkgb 提取碼:kkgb 如何回測k線圖 如何根據形態選股

解決 springboot + JPA + MySQL 表名全大寫 出現 “表不存在” 問題(Table ‘XXX.xxx‘ doesn‘t exist)

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 項目中使用 JPA 和 mysql 。表名是全大寫的。 出現 如下報錯&#xff1a; java.sql.SQLSyntaxErrorException: Table XXX_ms.work_tas…

自學Linux命令的四種方法

本文由 極客范 - 小道空空 翻譯自 Danny Stieben。歡迎加入極客翻譯小組&#xff0c;同我們一道翻譯與分享。轉載請參見文章末尾處的要求。如果你想成為Linux高手&#xff0c;那么掌握一些Linux命令是必不可少的。下面是自學Linux命令的四種方法。 每日提示 學習Linux命令的…

第五周學習總結

第六章&#xff1a; 主要內容: 1.接口 2.實現接口 3.理解接口 4.接口回調 5.接口與多態 6.接口變量做參數 7.面向接口編程 Example6_1: Example6_2: Example6_3: Example6_4: Example6_5: Example6_6: 總結&#xff1a;這章節沒有較大問題&#xff0c;例題也都做了一遍。蠻順利…

Android 設備的CPU類型(通常稱為”ABIs”)

armeabiv-v7a: 第7代及以上的 ARM 處理器。2011年15月以后的生產的大部分Android設備都使用它.arm64-v8a: 第8代、64位ARM處理器&#xff0c;很少設備&#xff0c;三星 Galaxy S6是其中之一。armeabi: 第5代、第6代的ARM處理器&#xff0c;早期的手機用的比較多。x86: 平板、模…

國信證券學習系列(1)

軟件不錯&#xff0c;滿足了我對股票&#xff0c;期貨&#xff0c;期權的全部要求。而且數據可以提供下載&#xff0c;簡直沒話說了。 數據清洗問題&#xff0c;我其實很早以前就在思考這個問題&#xff0c;回測&#xff0c;到底在測什么&#xff1f;什么樣的數據可以用來回測&…

JNA—JNI終結者

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 1.介紹 給大家介紹一個最新的訪問本機代碼的Java框架—JNA。 JNA(Java Native Access)框架是一個開源的Java框架&#xff0c;是SUN公司…

FIFO存儲器

FIFO( First Input First Output)簡單說就是指先進先出。由于微電子技術的飛速發展&#xff0c;新一代FIFO芯片容量越來越大&#xff0c;體積越來越小&#xff0c;價格越來越便宜。作為一種新型大規模集成電路&#xff0c;FIFO芯片以其靈活、方便、高效的特性&#xff0c;逐漸在…

通過8個技巧讓你成為一個超強的Linux終端用戶

本文由 極客范 - minejo 翻譯自 Chris Hoffman。歡迎加入極客翻譯小組&#xff0c;同我們一道翻譯與分享。轉載請參見文章末尾處的要求。使用Linux終端不僅僅是只輸入命令。學習這些基本的技巧&#xff0c;你就會逐漸掌握Bash shell&#xff0c;這個在大多數Linux發行版上默認…

國信證券學習系列(2)

獲取指數池&#xff1a; def init(ContextInfo):#設置股票池stock300 ContextInfo.get_stock_list_in_sector(滬深300)ContextInfo.stock300_weight {}stock300_symbol []stock300_weightlist [] ContextInfo.index_code ContextInfo.stockcode"."ContextInfo.m…

旅游服務商Bikego完成A輪融資,共建創投、馬蜂窩投資

2月26日消息&#xff0c;近日Bikego宣布完成A輪融資&#xff0c;共建創投、北京馬蜂窩之旅國際旅行社投資。目前金額尚未公開。 bikego領趣旅行成立于2016年&#xff0c;是一家目的地日游服務運營商。從內容切入&#xff0c;提供國內自由行客戶的白天玩法解決方案&#xff0c;…

python-flask-1

https://askubuntu.com/questions/244641/how-to-set-up-and-use-a-virtual-python-environment-in-ubuntu 1. virtualenv安裝 sudo apt-get install virtualenv sudo apt install virtualenvwrapper echo "source /usr/share/virtualenvwrapper/virtualenvwrapper.sh&quo…

JSch:Java Secure Channel -- java 代碼實現 ssh 遠程操作

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 JSch 是SSH2的一個純Java實現。 它允許你連接到一個 sshd 服務器&#xff0c;使用端口轉發&#xff0c;X11轉發&#xff0c;文件傳輸等…

國信證券學習系列(3)

日內回轉策略&#xff1a;做T策略 擇時交易&#xff1a; if date[-8:-3] ! 14:55:if macd > 0 and macd_pre < 0:# 根據MACD>0則開倉,小于0則平倉if avaliable > df.iloc[-1, 0] * ContextInfo.Lots * 100:order_shares(ContextInfo.get_universe()[0], ContextIn…

時序數據庫連載系列: 時序數據庫一哥InfluxDB之存儲機制解析

2019獨角獸企業重金招聘Python工程師標準>>> InfluxDB 的存儲機制解析 本文介紹了InfluxDB對于時序數據的存儲/索引的設計。由于InfluxDB的集群版已在0.12版就不再開源&#xff0c;因此如無特殊說明&#xff0c;本文的介紹對象都是指 InfluxDB 單機版 1. InfluxDB 的…