题目大意:
询问一棵树上两点之间的边权和or第k个点是多少
link-cut tree
一开始把第k个点看成了第k大的边……吓了我一跳……
边权处理方法类似QTREE,再维护一个sum一个size就行了……
犯了脑残错误……调了半小时……
//Lib #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<ctime> #include<iostream> #include<algorithm> #include<vector> #include<string> #include<queue> using namespace std; //Macro #define rep(i,a,b) for(int i=a,tt=b;i<=tt;++i) #define rrep(i,a,b) for(int i=a,tt=b;i>=tt;--i) #define erep(i,e,x) for(int i=x;i;i=e[i].next) #define irep(i,x) for(__typedef(x.begin()) i=x.begin();i!=x.end();i++) #define read() (strtol(ipos,&ipos,10)) #define sqr(x) ((x)*(x)) #define pb push_back #define PS system("pause"); typedef long long ll; typedef pair<int,int> pii; const int oo=~0U>>1; const double inf=1e20; const double eps=1e-6; string name="",in=".in",out=".out"; //Var struct T { int LC,RC,FA,SIZE,KEY,SUM; void set(){LC=RC=FA=SIZE=KEY=SUM=0;} #define lc(x) tree[x].LC #define rc(x) tree[x].RC #define fa(x) tree[x].FA #define size(x) tree[x].SIZE #define key(x) tree[x].KEY #define sum(x) tree[x].SUM }tree[10008]; struct E { int node,next,v; }e[20008]; int n,m,T; int h[10008],tot; void add(int a,int b,int c){e[++tot].next=h[a];e[tot].node=b;e[tot].v=c;h[a]=tot;} void DFS(int x,int fa) { int y; erep(i,e,h[x])if((y=e[i].node)!=fa) { key(y)=e[i].v;fa(y)=x;DFS(y,x); } } void Update(int x) { sum(x)=sum(lc(x))+sum(rc(x))+key(x); size(x)=size(lc(x))+size(rc(x))+1; } void Zig(int x) { int y=fa(x),z=fa(y); if(lc(z)==y)lc(z)=x;else if(rc(z)==y)rc(z)=x;fa(x)=z; fa(rc(x))=y;lc(y)=rc(x);rc(x)=y;fa(y)=x; Update(y); } void Zag(int x) { int y=fa(x),z=fa(y); if(lc(z)==y)lc(z)=x;else if(rc(z)==y)rc(z)=x;fa(x)=z; fa(lc(x))=y;rc(y)=lc(x);lc(x)=y;fa(y)=x; Update(y); } bool isRoot(int x){return lc(fa(x))!=x&&rc(fa(x))!=x;} void Splay(int x) { for(int y,z;!isRoot(x);) { y=fa(x);z=fa(y); if(isRoot(y)) if(lc(y)==x)Zig(x); else Zag(x); else if(lc(z)==y) if(lc(y)==x)Zig(y),Zig(x); else Zag(x),Zig(x); else if(rc(y)==x)Zag(y),Zag(x); else Zig(x),Zag(x); } Update(x); } void Expose(int x){for(int y=0;x;x=fa(x)){Splay(x);rc(x)=y;Update(x);y=x;}} int Find(int root,int k) { while(1) { if(size(lc(root))+1==k)return root; if(size(lc(root))>=k)root=lc(root); else{k-=size(lc(root))+1;root=rc(root);} } } int Query(int x,int y,int z=0) { Expose(y); for(y=0;x;x=fa(x)) { Splay(x);if(!fa(x))break;rc(x)=y;Update(x);y=x; } if(z==0)return sum(rc(x))+sum(y); if(size(y)>=z)return Find(y,size(y)-z+1); else if(size(y)+1==z)return x; else {z-=size(y)+1;return Find(rc(x),z);} } void Init() { scanf("%d",&n);int a,b,c; rep(i,1,n)h[i]=0,tree[i].set();tot=1; rep(i,1,n-1) { scanf("%d%d%d",&a,&b,&c); add(a,b,c),add(b,a,c); } DFS(1,0); } void Work() { int a,b,c;char ch[10]; while(1) { scanf("%s",ch); if(ch[1]=='O')return; scanf("%d%d",&a,&b); if(ch[1]=='I')printf("%d\n",Query(a,b)); else scanf("%d",&c),printf("%d\n",Query(a,b,c)); } } int main() { // freopen((name+in).c_str(),"r",stdin); // freopen((name+out).c_str(),"w",stdout); for(scanf("%d",&T);T;T--) { Init(); Work(); } return 0; }
您还没有登录,请您登录后再发表评论
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
My solution for some spoj problems
Online Judge Problem solution VN.SPOJ
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
SPOJ 应对spoj.com的挑战
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...
RandomGoCode:算法,SPOJ,涂鸦...但是在Go中!
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
2.12 求 A B 的约数之和对 MOD 取模 . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.13 莫比乌斯反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.13.1 莫比乌斯...
SPOJ( )上选定问题的解决方案
杨弋SPOJ做题表格
SPOJ 解决来自难题
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
Spoj 用户工具基于 Django 的 Spoj 用户分析工具。 目前托管在 Google Appengine 上: ://spojtool.appspot.com/安装获取列出的包,并将它们放在指定的项目目录中。 为了安全,请修改 secret_key.py 中的 SECRET_KEY...
HướngdẫnvàchiasẻlờigiảichocácProblemstrênvn.spoj.com。 发展 确保没有在计算机上安装Ruby sudo apt install ruby ruby-dev 安装jekyll主题或直接键入 gem install bundler jekyll 在gem中安装软件包...
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
SPOJ-Solutions:SPOJ算法问题的解决方案
spoj MSTS kruskal +生成树
相关推荐
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
My solution for some spoj problems
Online Judge Problem solution VN.SPOJ
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
SPOJ 应对spoj.com的挑战
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...
RandomGoCode:算法,SPOJ,涂鸦...但是在Go中!
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
2.12 求 A B 的约数之和对 MOD 取模 . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.13 莫比乌斯反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.13.1 莫比乌斯...
SPOJ( )上选定问题的解决方案
杨弋SPOJ做题表格
SPOJ 解决来自难题
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
Spoj 用户工具基于 Django 的 Spoj 用户分析工具。 目前托管在 Google Appengine 上: ://spojtool.appspot.com/安装获取列出的包,并将它们放在指定的项目目录中。 为了安全,请修改 secret_key.py 中的 SECRET_KEY...
HướngdẫnvàchiasẻlờigiảichocácProblemstrênvn.spoj.com。 发展 确保没有在计算机上安装Ruby sudo apt install ruby ruby-dev 安装jekyll主题或直接键入 gem install bundler jekyll 在gem中安装软件包...
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
SPOJ-Solutions:SPOJ算法问题的解决方案
spoj MSTS kruskal +生成树