洛谷P4211 LCA

2022-09-23 02:12:08 字數 1632 閱讀 2258

給出一個 \(n\) 個節點的有根樹(編號為 \(0\) 到 \(n-1\),根節點為 \(0\))。

一個點的深度定義為這個節點到根的距離 \(+1\)。

設 \(dep[i]\) 表示點i的深度,\(lca(i,j)\) 表示 \(i\) 與 \(j\) 的最近公共祖先。

有 \(q\) 次詢問,每次詢問給出 \(l\ r\ z\),求 \(\sum_^r dep[lca(i,z)]\) 。

首先 \(dep[lca(x,y)]\) 等價於把 \(x\) 的所有祖先節點標記為 1,然後求 \(y\) 的祖先節點的權值和。

那麼 \(\sum^_ dep[lca(x,i)]\) 等價於把 \([l,r]\) 的所有點的祖先節點全部加一,求 \(x\) 的祖先節點的權值和。

把詢問拆成 \(1\sim r\) 的和減去 \(1\sim l-1\) 的和,然後按照編號從小到大列舉點,樹剖 + 線段樹將這個點到 1 的路徑的點權值全部加一。

對於詢問就直接求到 1 的權值和即可。

時間複雜度 \(o(n\log^2 n)\)。

#include #include #include #include using namespace std;

const int n=50010,mod=201314;

int head[n],son[n],fa[n],size[n],id[n],rk[n],top[n];

int n,q,tot;

vectorpos[n];

struct edge

e[n];

struct query

ask[n];

void add(int from,int to)

void dfs1(int x)

}void dfs2(int x,int tp)

}struct segtree }

void build(int x,int ql,int qr)

void pushup(int x)

void update(int x,int ql,int qr)

pushdown(x);

int mid=(l[x]+r[x])>>1;

if (qr<=mid) update(x*2,ql,qr);

else if (ql>mid) update(x*2+1,ql,qr);

else update(x*2,ql,mid),update(x*2+1,mid+1,qr);

pushup(x); }

int query(int x,int ql,int qr)

}seg;

void update(int x)

}int query(int x)

return ans;

}int main()

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

tot=0;

dfs1(1); dfs2(1,1);

seg.build(1,1,n);

for (int i=0;i<=n;i++) }

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

printf("%d\n",(ask[i].ans%mod+mod)%mod);

return 0;

}

P4211 LNOI2014 LCA

連結分析 首先一種比較有趣的轉化是,將所有點到1的路徑上都 1,然後z到1的路徑上的和,就是所有答案的deep的和。 對於多次詢問,要麼考慮...

P4211 LNOI2014 LCA LCT

loj luogu 多次詢問 sum limits dep lca i z 可以轉化成l到r上的點到根的路徑 1 最後求一下1到z的路徑和就...

luogu P4211 LNOI2014 LCA

題面傳送門 一道典型的樹剖題目。 這東西如果暴力肯定是沒法算的。除非能轉化一下,比如算貢獻。 然後會發現hhhoj上有一道題和這個很像。 這樣的話可以把每個點向上算貢獻,一直加 1 到根節點。 這樣當一個點加到時那麼就自然算到了貢獻。 其實質是差分,只不過沒那麼明顯罷了。 這個東西可以用樹剖 線段樹...