洛谷P6135 模板 虛樹

2022-09-23 02:32:13 字數 1327 閱讀 7049

給定一棵 \(n\) 個點的有根樹,樹上有 \(k\) 個關鍵點,請你構建這些點的虛樹。

\(\operatorname\)本解法不是虛樹的一般解法,只是詢問只有一組,所以就直接在 dfs 中做完詢問。如果本題有 \(m\) 組詢問,那依然要用一般方法,否則時間複雜度為 \(o(nm\log n)\)。

虛樹指的是一棵僅包含這些關鍵節點以及他們兩兩之間的 lca 的樹。其中一條樹邊的權值為原樹的兩點之間權值之和。

考慮用 dfs 遍歷原樹,用一個棧維護從根節點到最近一次到達的關鍵節點之間的關鍵節點路徑。例如下圖

藍色節點為關鍵節點,假設我們現在遍歷到 4,那麼棧 \(s=[1,3,4]\)。

當我們遍歷到一個關鍵節點 \(x\) 時,設棧頂元素為 \(y\),\(x,y\) 的 lca 為 \(p\)。

最後 dfs 完畢時將棧內的元素再次兩兩連邊即可。時間複雜度 \(o(n\log n)\)。

為了防止棧中沒有元素,我們可以現在棧中插入 0 當做一個超級根。

#include #include #include using namespace std;

const int n=200010,lg=20;

int n,m,tot,top,rt,fa[n],head[n],s[n],f[n][lg+1],dep[n];

bool key[n];

struct edge

e[n];

void add(int from,int to)

int lca(int x,int y)

void dfs(int x,int ff)

fa[s[top]]=p; top--;

if (s[top]!=p) s[++top]=p;

} s[++top]=x;

} for (int i=head[x];~i;i=e[i].next)

dfs(e[i].to,x);

}int main()

for (int i=1,x;i<=m;i++)

memset(fa,-1,sizeof(fa));

top=1;

dfs(rt,0);

for (int i=top;i>=1;i--)

fa[s[i]]=s[i-1];

for (int i=1;i<=n;i++)

if (fa[i]==-1) printf("-1 -1\n");

else if (!fa[i]) printf("0 0\n");

else printf("%d %d\n",fa[i],dep[i]-dep[fa[i]]);

return 0;

}

洛谷P3378 模板 堆

如題,初始小根堆為空,我們需要支援以下3種操作 操作1 1 x 表示將x插入到堆中 操作2 2 輸出該小根堆內的最小數 操作3 3 刪除該小...

洛谷 P3378 模板 堆

如題,初始小根堆為空,我們需要支援以下3種操作 操作1 1 x 表示將x插入到堆中 操作2 2 輸出該小根堆內的最小數 操作3 3 刪除該小...

P3378 堆 模板 洛谷

如題,初始小根堆為空,我們需要支援以下3種操作 操作1 1 x 表示將x插入到堆中 操作2 2 輸出該小根堆內的最小數 操作3 3 刪除該小根堆內的最小數 輸入格式 第一行包含一個整數n,表示操作的個數 接下來n行,每行包含1個或2個正整數,表示三種操作,格式如下 操作1 1 x 操作2 2 操作3...