[HEOI2014] 大工程

来源:https://www.cnblogs.com/nosta/archive/2019/01/11/10256658.html
-Advertisement-
Play Games

「題意」給你一棵樹,每次詢問若在在選中的k個點兩兩連接無相邊,邊權為原來樹上的點對距離,求這些邊的:1)權值和 2)最短的邊 3)最長的邊。所有k之和$\le$2 n。 「分析」虛樹模板題。(但是獨立寫出來還是很振奮人心的合)直接考慮對虛樹dp,設pmn[x]為x到x的子樹內的關鍵點的最短距離,pm ...


「題意」給你一棵樹,每次詢問若在在選中的k個點兩兩連接無相邊,邊權為原來樹上的點對距離,求這些邊的:1)權值和 2)最短的邊 3)最長的邊。所有k之和$\le$2*n。
「分析」虛樹模板題。(但是獨立寫出來還是很振奮人心的合)直接考慮對虛樹dp,設pmn[x]為x到x的子樹內的關鍵點的最短距離,pmx[x]為最長距離,sum[x]為x到子樹內所有關鍵點的距離之和。這些都很好處理。統計答案利用樹形dp的常用技巧——有當前子樹和以前的子樹進行組合。

「實現」

/*
    寫對啦!woc
*/

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+10;
const int inf=0x3f3f3f3f;

int n,q,k;
int dfn[N],dep[N],fa[N][20];
vector<int> e[N];

void pre(int x,int pa) {
    static int cnt=0;
    dfn[x]=++cnt;
    dep[x]=dep[fa[x][0]=pa]+1;
    for(int i=1; (1<<i)<=dep[x]; ++i) 
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(unsigned i=0; i<e[x].size(); ++i)
        if(e[x][i]!=pa) pre(e[x][i],x);
}
int lca(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    int dif=dep[x]-dep[y];
    for(int i=19; ~i; --i) 
        if(dif&(1<<i)) x=fa[x][i];
    if(x==y) return x;
    for(int i=19; ~i; --i) 
        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

int a[N],s[N],top,cnt;
int head[N],to[N<<1],len[N<<1],last[N<<1];
void add_edge(int x,int y,int w) {
    to[++cnt]=y;
    len[cnt]=w;
    last[cnt]=head[x];
    head[x]=cnt;
}
bool cmp(int x,int y) {
    return dfn[x]<dfn[y];
}
void ist(int x) {
    if(top==1) {
        if(x!=1) s[++top]=x; 
        return;
    }
    int t=lca(s[top],x);
    if(t!=s[top]) {
        for(; top>1&&dfn[s[top-1]]>=dfn[t]; top--) 
            add_edge(s[top-1],s[top],dep[s[top]]-dep[s[top-1]]);
        if(t!=s[top]) add_edge(t,s[top],dep[s[top]]-dep[t]), s[top]=t;
    }
    s[++top]=x;
}

bool mark[N];
LL lmn[N],lmx[N],siz[N],sum[N];
LL pum,pmn,pmx;

void dfs(int x) {
    lmn[x]=inf;
    lmx[x]=-inf;
    sum[x]=siz[x]=0;
    if(mark[x]) {
        lmx[x]=lmn[x]=0;
        siz[x]=1;
    }
    for(int i=head[x]; i; i=last[i]) {
        dfs(to[i]);
        pmn=min(pmn,lmn[x]+lmn[to[i]]+len[i]);
        pmx=max(pmx,lmx[x]+lmx[to[i]]+len[i]);
        pum+=sum[x]*siz[to[i]]
            +(siz[x]-mark[x])*sum[to[i]]
            +(siz[x]-mark[x])*len[i]*siz[to[i]];
        lmn[x]=min(lmn[x],lmn[to[i]]+len[i]);
        lmx[x]=max(lmx[x],lmx[to[i]]+len[i]);
        sum[x]+=sum[to[i]]+siz[to[i]]*len[i];
        siz[x]+=siz[to[i]];
    }
    if(mark[x]) pum+=sum[x];
    head[x]=0;
    mark[x]=0;
}

void print() {
printf("asphaush tree: \n");
    static queue<int> Q;
    Q.push(1);
    while(!Q.empty()) {
        int x=Q.front(); Q.pop();
        for(int i=head[x]; i; i=last[i]) {
            printf("%d -> %d, length is %d\n",x,to[i],len[i]);
            Q.push(to[i]);
        }
    }
}

void solve() {
//printf("\nnew solving case: \n");
    scanf("%d",&k);
    for(int i=1; i<=k; ++i) {
        scanf("%d",&a[i]);
        mark[a[i]]=true;
    }
    sort(a+1,a+k+1,cmp);
    cnt=0;
    s[top=1]=1;
    for(int i=1; i<=k; ++i) ist(a[i]);
    for(; top>1; top--)
        add_edge(s[top-1],s[top],dep[s[top]]-dep[s[top-1]]);
//    print();
    pum=0;
    pmn=inf;
    pmx=-inf;
    dfs(1);
    printf("%lld %lld %lld\n",pum,pmn,pmx);
}

int main() {
    scanf("%d",&n);
    for(int x,y,i=n; --i; ) {
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    pre(1,0);
    scanf("%d",&q);
    while(q--) solve();
    return 0;
}

/*
10 
2 1 
3 2 
4 1 
5 2 
6 4 
7 5
8 6 
9 7 
10 9 

5 

2 
5 4 

2 
10 4 

2 
5 2 

2 
6 1 

2 
6 1
*/

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

-Advertisement-
Play Games
更多相關文章
  • 下麵是常用的幾個系統類的常用方法整理: list: 列表[1, 2,...] set: 集合,無重覆元素{1, 2,...} str: 字元串 dict: 字典{a:'a', b:'b',...} TextIOWrapper: 文件對象 子集測試(允許不嚴格意義上的子集): 集合中所有的元素都是 t ...
  • 1 JDK安裝 zookeeper是運行在JDK環境下的,安裝zookeeper前需要安裝JDK 下載linux的 jdk1.8.tar,上傳至linux伺服器 解壓縮jdk,配置jdk tar -zxvf 解壓縮jdk 將jdk1.8.0_191重命名為jdk8 mv jdk1.8.0_191/ ...
  • 定義資料庫 在Django中使用多個資料庫的第一步是告訴Django您將要使用的資料庫伺服器。 資料庫可以有您選擇的任何別名。但是,別名 default 有著特殊的意義。Django使用別名為 default 為預設資料庫。 例如 settings.py 定義兩個資料庫,預設 PostgreSQL ...
  • 安裝虛擬環境的命令如下: sudo pip install virtualenv sudo pip install virtualenvwrapper 創建虛擬環境的命令如下: mkvirtualenv 虛擬環境名稱 例: mkvirtualenv hj_django 退出虛擬環境的命令如下: de ...
  • for 迴圈 功能 for 迴圈是一種迭代迴圈機制,迭代即重覆相同的邏輯操作,每次的操作都是基於上一次的結果而進行的。並且for迴圈可以遍歷任何序列的項目,如一個列表或者一個字元串 語法 for 迴圈的一般格式如下: for <variable> in <sequence> <staements> ...
  • Python入門 以下主要講述Python的一些基礎語法,包含行的縮進在python中的重要意義,python中常見的保留字和引號的使用,如何實現單行註釋和多行註釋。 print("hello,Python!") 第一個Python程式 我們在創建python文件時,所有的文件必須以.py為拓展名。 ...
  • a)ThresholdFilter屬性:onMatch表示匹配設定的日誌級別後是DENY還是ACCEPT,onMismatch表示不匹配設定的日誌級別是DENY還是ACCEPT還是NEUTRAL b)上面說的match/misMatch指的是高於或等於設定的日誌級別。所以,要先定義日誌級別高的Fil... ...
  • 1.簡介 Phoenix是一個HBase框架,可以通過SQL的方式來操作HBase。 Phoenix是構建在HBase上的一個SQL層,是內嵌在HBase中的JDBC驅動,能夠讓用戶使用標準的JDBC來操作HBase。 Phoenix使用JAVA語言進行編寫,其查詢引擎會將SQL查詢語句轉換成一個或 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...