八中鏈接 http://www.zybbs.org/JudgeOnline/problem.php?id=1103
原題鏈接 http://main.edu.pl/en/archive/oi/14/meg
題目大意:給你一棵樹(仔細揣摩題目描述,是樹),邊有權(1或0),每個詢問問從1到x的路徑上權值和是多少。
看完我就在想LCT亂搞……然后發現LCT有點高射炮打蚊子了。后來發現這個題可以線性維護DFS序列來做,用線段樹。
(PS:其實我寫樹狀數組…………)
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #define mn 250002 #define lowbit(x) (x)&(-x) using namespace std; pair<int,int> pos[mn]; int n,m,a,b,node=0,s[mn*2]; char sym[2]; bool vis[mn]; struct EDGE{ int pnt; EDGE *pre; EDGE(){} EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){} }Edge[mn*2],*SP=Edge,*edge[mn]; inline void addedge(int a,int b){ edge[a]=new(++SP)EDGE(b,edge[a]); edge[b]=new(++SP)EDGE(a,edge[b]); } void Modify(int x,int val){ while(x<=n) s[x]+=val,x+=lowbit(x); } int Query(int x){ int sum=0; while(x>0) sum+=s[x],x-=lowbit(x); return sum; } void dfs(int x){ pos[x].first=++node; Modify(node,1); vis[x]=true; for(EDGE *j=edge[x];j;j=j->pre) if(!vis[j->pnt]) dfs(j->pnt); pos[x].second=++node; Modify(node,-1); } int main(){ scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d",&a,&b); addedge(a,b); } n<<=1; dfs(1); scanf("%d",&m); while(m){ scanf("%s",sym); if(sym[0]=='W'){ scanf("%d",&a); printf("%d\n",Query(pos[a].first)-1); m--; }else{ scanf("%d%d",&a,&b); Modify(pos[b].first,-1); Modify(pos[b].second,1); } } return 0; }
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
