HDU 4812 D Tree

HDU 4812?

思路:

點分治

先預處理好1e6 + 3以內到逆元

然后用map 映射以分治點為起點的鏈的值a 成他的下標 u?

然后暴力跑出以分治點兒子為起點的鏈的值b,然后在map里查找inv[b]*k

代碼:

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//headconst int MOD = 1e6 + 3;
const int INF = 0x7f7f7f7f;
const int N = 1e5 + 5;
int inv[MOD + 5], mp[MOD + 5], head[N], mxsz[N], sz[N], v[N], cnt = 0, rt = 0, n, k, ans1, ans2;
int deep[N], dis[N], id[N], top = 0;
bool vis[N];
struct edge {int to, nxt;
}edge[N*2];
void add_edge(int u, int v) {edge[cnt].to = v;edge[cnt].nxt = head[u];head[u] = cnt++;
}
void init() {inv[1] = 1;for (int i = 2; i < MOD; i++) inv[i] = (MOD - MOD/i) * 1LL * inv[MOD%i] % MOD;
}
void update(int x, int y) {int t = (1LL * inv[x] * k) % MOD;int now = mp[t];if(!now) return ;if(now > y) swap(now, y);if(now < ans1 || now == ans1 && y < ans2) ans1 = now, ans2 = y;
}
void get_rt(int o, int u) {sz[u] = 1, mxsz[u] = 0;for (int i = head[u]; ~i; i = edge[i].nxt) {if(edge[i].to != o && !vis[edge[i].to]) {get_rt(u, edge[i].to);sz[u] += sz[edge[i].to];mxsz[u] = max(mxsz[u], sz[edge[i].to]);}}mxsz[u] = max(mxsz[u], n - sz[u]);if(mxsz[u] < mxsz[rt]) rt = u;
}
void get_d(int o, int u) {deep[++top] = dis[u];id[top] = u;for (int i = head[u]; ~i; i = edge[i].nxt) {if(!vis[edge[i].to] && edge[i].to != o) {dis[edge[i].to] = (1LL * dis[u] * v[edge[i].to])%MOD;get_d(u, edge[i].to);}}
}
void solve(int u) {vis[u] = true;mp[v[u]] = u;for (int i = head[u]; ~i; i = edge[i].nxt) {if(!vis[edge[i].to]) {top = 0, dis[edge[i].to] = v[edge[i].to];get_d(u, edge[i].to);for (int j = 1; j <= top; j++) update(deep[j], id[j]);top = 0, dis[edge[i].to] = (1LL * v[u] * v[edge[i].to])%MOD;get_d(u, edge[i].to);for (int j = 1; j <= top; j++) {int t = deep[j];if(!mp[t] || id[j] < mp[t]) mp[t] = id[j];}}}mp[v[u]] = 0;for (int i = head[u]; ~i; i = edge[i].nxt) {if(!vis[edge[i].to]) {top = 0, dis[edge[i].to] = (1LL * v[u] * v[edge[i].to])%MOD;get_d(u, edge[i].to);for (int j = 1; j <= top; j++) mp[deep[j]] = 0;}}for (int i = head[u]; ~i; i = edge[i].nxt) {if(!vis[edge[i].to]) {mxsz[0] = n =  sz[edge[i].to];get_rt(rt = 0, edge[i].to);solve(rt);}}
}
int main() {init();int u, V;while(~scanf("%d%d", &n, &k)) {mem(head, -1);mem(vis, false);mem(mp, 0);cnt = 0;ans1 = ans2 = INF;for (int i = 1; i <= n; i++) scanf("%d", &v[i]);for (int i = 1; i < n; i++) scanf("%d%d", &u, &V), add_edge(u, V), add_edge(V, u);mxsz[0] = n;get_rt(rt = 0, 1);solve(rt);if(ans1 == INF) printf("No solution\n");else printf("%d %d\n", ans1, ans2);}return 0;
}

?

轉載于:https://www.cnblogs.com/widsom/p/9106507.html

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

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

相關文章

Angular CLI 安裝

安裝Angular 官網的教程&#xff0c;因為國內網絡環境原因&#xff0c;訪問不了服務器&#xff0c;導致安裝失敗。 1、先安裝NodeJs 安裝教程&#xff1a;http://blog.csdn.net/zengmingen/article/details/72650484 2、通過NodeJs中的模塊npm 命令行安裝 CLI 2.1、設置npm的…

go 寫文件_「go」 項目多個文件編程

golang 學習的時候很多sample 講的都是一個文件的go 文件怎么寫&#xff0c;但是現實中不可能所有的實現都寫到一個文件里面&#xff0c;按照功能的不同&#xff0c;要么拆分成不同的文件&#xff0c;要么拆分成不同的文件。下面有些個人的經驗分享下&#xff0c;如果有問題請指…

CycleGAN 各種變變變

轉載自 簡單介紹了一下GAN和DCGAN的原理。以及如何使用Tensorflow做一個簡單的生成圖片的demo。 Ian Goodfellow對GAN一系列工作總結的ppt&#xff0c;確實精彩&#xff0c;推薦&#xff1a;獨家 | GAN之父NIPS 2016演講現場直擊&#xff1a;全方位解讀生成對抗網絡的原理及未來…

pycharm與webstorm 2017 激活破解

原有的方式已經失效&#xff0c;見下面博文&#xff1a; https://blog.csdn.net/justszh/article/details/81484802

mysql blob 比較_與MSSQL對比學習MYSQL的心得(四)--BLOB數據類型

MYSQL里的BLOB數據類型BLOB是一個二進制大對象&#xff0c;用來存儲可變數量的數據。BLOB類型分為4種&#xff1a;TinyBlob、Blob、MediumBlob、LongBlob&#xff0c;這幾個類型之間的唯一區別是在存儲文件的最大大小上不同。MySQL的四種BLOB類型 類型 大小(單位&#xff1…

Webstorm常用快捷鍵

webstrom 使用 eclipse快鍵鍵 File--settings keymap 選擇 eclipse 原文鏈接&#xff1a;http://www.cnblogs.com/yeminglong/p/5995421.html ------------------以下是webstrom默認的----------------------------------- Ctrl/ 或 CtrlShift/ 注釋&#xff08;// 或者/…

VirtualBox 上安裝Debian 后分辨率設置

VirtualBox 上安裝Debian 后分辨率設置 首先要配置source.list打開終端&#xff0c; su 切換成root用戶&#xff0c; cd /etc/apt 然后編輯source.list rootdebian:/etc/apt# vi source.list 注釋deb cdrom:行&#xff0c;加以下源 deb http://deb.debian.org/debian stretc…

瘋狂的程序員_程序員的樂趣是什么?

作者&#xff1a;Java3y我是一個程序員&#xff0c;外行人都以為我是修電腦的&#xff0c;我笑了笑&#xff0c;隨意ctrl cctrl v了一把&#xff0c;想象著你們因為我的文章而開心不止&#xff0c;我感到充實而欣慰。想象著你們給我拼命點贊的樣子&#xff0c;是多么的滑稽&…

template多行編寫的方式

模板是包在 ECMAScript 2015 反引號 () 中的一個多行字符串。 反引號 () — 注意&#xff0c;不是單引號 () — 允許把一個字符串寫在多行上&#xff0c; 使 HTML 模板更容易閱讀。 反引號&#xff1a;鍵盤數字鍵1 旁邊的&#xff0c;ESC鍵下面的鍵 如果單引號 Component({sel…

sqllite事務和MySQL事務_Android學習---SQLite數據庫的增刪改查和事務(transaction)調用...

上一篇文章中介紹了手工拼寫sql語句進行數據庫的CRUD操作,本文將介紹調用sqlite內置的方法實現CRUD操作,其實質也是通過拼寫sql語句.首先,創建一個新的android項目:其次,查看代碼實現增刪查改:1.創建DB工具類MyDBHelper.java(創建數據庫的操作)packagecom.amos.android_db;impo…

sqlserver2000給賬戶授予所有的權限_你的位置信息權限設置對了么?

位置信息權限是眾多應用權限中的一種&#xff0c;是應用獲取手機地理位置信息的必要憑證。在你首次安裝應用并打開時&#xff0c;通常會出現一連串的權限彈框&#xff0c;如果該應用在其運行過程中會用到你的地理位置信息&#xff0c;那么這些彈框中就會包含一個與位置信息有關…

Python之路,Day1 - Python基礎1

本節內容 Python介紹發展史Python 2 or 3?安裝Hello World程序變量用戶輸入模塊初識.pyc是個什么鬼&#xff1f;數據類型初識數據運算表達式if ...else語句表達式for 循環break and continue 表達式while 循環作業需求 一、 Python介紹 python的創始人為吉多范羅蘇姆&#xf…

mysql 范式化_MySQL-范式和反范式

1.第一范式(1NF)(列不能再拆分)原子性&#xff0c;字段不可分(列的信息)&#xff0c;只要是關系型數據庫&#xff0c;就自動滿足1NF&#xff1b;2.第二范式(2NF)(主鍵唯一&#xff0c;且被依賴)在第一范式基礎上建立的&#xff0c;即滿足第二范式的必須先滿足第一范式。要求DB表…

端口被占用解決辦法

1. 端口被占用解決辦法 netstat -ano | findstr 8080(端口號) taskkill -pid (進程pid) –f轉載于:https://www.cnblogs.com/xaoco/p/9114773.html

java 判斷是否是list_JAVA從頭開始一基礎梳理(4-3)

大家好&#xff0c;今天我們介紹一下java中常用的集合類型。首先&#xff0c;我們先看一下java中集合類型的結構。以上是集合的繼承關系圖&#xff0c;通常我們使用的比較多的是 Set , List , Map以及其衍生的子類和接口實現類。首先給大家介紹一下List&#xff0c;List本身是一…

Python2.x還是3.x?

2.x 和 3.x對于程序員的編碼來說&#xff0c;沒有發生太大的變化&#xff0c;當然也是有變化的&#xff0c;主要是Python內部發生了巨變。 要用3.x的原因是&#xff1a; 1、3.x和2.x版本不兼容。 2、Python庫新增的內容不支持2.x了。 3、2.x版本官方支持到2020年結束。 晚改…

前端網頁廣告無線翻滾_從小白到web前端工程師進階之路 從0到1到更深

互聯網的發展&#xff0c;讓web前端技術發生了翻天覆地的變化&#xff0c;前端開發工程師可以讓網頁內容變得更加生動&#xff0c;為用戶帶來更好的體驗。那么&#xff0c;武漢web前端培訓哪個好&#xff1f;web前端好學嗎&#xff1f;作為一個合格的Web前端工程師&#xff0c;…

PowerDesigner導出表為Excel(轉)

打開腳本運行器CtrlShiftX 導出&#xff1a; ****************************************************************************** Option ExplicitDim rowsNumrowsNum 0 -----------------------------------------------------------------------------Main function -------…

判讀一個對象不為空_ArrayList實現分析(一)——對象創建

ArrayList是java中最常用的集合類之一&#xff0c;它的內部實現是基于數組&#xff0c;因此ArryList可以根據索引實現隨機訪問。ArryList繼承了AbstractList類&#xff0c;并且實現了List, RandomAccess, Cloneable接口。下面詳細分析一下ArrayList的實現&#xff0c;下面的分析…

AngularJS與Angular的區別

指同一事物&#xff0c;版本的區別&#xff0c;叫法不同 Angular2.0之前的版本&#xff08;1.x&#xff09;叫做AngularJS 1.x的使用是引入AngularJS的js文件到網頁。 2.0之后&#xff0c;就是完全不同了。 Angular2.x與Angular1.x 的區別類似 Java 和 JavaScript 或者說是…