如题= =自用模板

ST算法和Tarjan算法和倍增算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//ST
import java.io.*;
import java.util.*;
public class Main {

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
PrintWriter pw=new PrintWriter(System.out);
int t=sc.nextInt();
LCA lca=new LCA();
while(sc.hasNext()){
int n=sc.nextInt();
int[]deg=new int[n+1];
lca.init();
for(int i=0;i<n-1;i++){
int x=sc.nextInt();
int y=sc.nextInt();
deg[y]++; //记录入度数
lca.adj[x].add(new Edge(x,y,1));
}
int s=0;
for(int i=1;i<=n;i++){
if(deg[i]==0)s=i; //找入度数为零的点作为起点 也可以加双向边自己定义根
}
lca.dfs(s, 0);
lca.st(); //不要忘记调用st
int u=sc.nextInt();
int v=sc.nextInt();
pw.println(lca.lca(u, v));
pw.flush();
}

}

}
class Edge{
int u;
int v;
int w;
Edge(int u,int v,int w){
this.u=u;
this.v=v;
this.w=w;
}
}
class LCA{
int maxn=10010;
int maxm=20; //2^20
ArrayList<Edge>[]adj;
int tot;
boolean[]vis;
int[]pow;
int[]first;
int[]R;
int[]ver;
int[]dir;
int[][]dp;
LCA(){
adj=new ArrayList[2*maxn];
for(int i=0;i<maxn;i++)adj[i]=new ArrayList<Edge>();
tot=0;
vis=new boolean[maxn];
dir=new int[maxn];
dp=new int[2*maxn][maxm];
ver=new int[2*maxn];
first=new int[maxn];
pow=new int[maxm];
R=new int[2*maxn];
pow[0]=1;
for(int i=1;i<maxm;i++){
pow[i]=pow[i-1]*2;
}
}
void init(){
for(int i=0;i<maxn;i++)adj[i].clear();
tot=0;
Arrays.fill(vis, false);
Arrays.fill(dir, 0);
Arrays.fill(ver, 0);
Arrays.fill(first, 0);
Arrays.fill(R, 0);
for(int i=0;i<2*maxn;i++)
for(int j=0;j<maxm;j++)dp[i][j]=0;
}
void dfs(int u ,int dep){
vis[u] = true; ver[++tot] = u; first[u] = tot; R[tot] = dep;
for(int k=0;k<adj[u].size();k++){
Edge child=adj[u].get(k);
if(!vis[child.v] ){
int v = child.v , w = child.w;
dir[v] = dir[u] + w;
dfs(v,dep+1);
ver[++tot] = u; R[tot] = dep;
}
}
}
void st(){
int len=tot;
int K = (int)(Math.log((double)(len)) / Math.log(2.0));
for(int i=1;i<=len;i++)dp[i][0]=i;
for(int j=1;j<=K;j++){
for(int i=1;i+pow[j]-1<=len;i++){
int a=dp[i][j-1];
int b=dp[i+pow[j-1]][j-1];
if(R[a]<R[b])dp[i][j]=a;
else dp[i][j]=b;
}
}
}
int lca(int u ,int v)
{
int x = first[u] , y = first[v];
if(x > y) {
int t=x;
x=y;
y=t;
}
int res = RMQ(x,y);
return ver[res];
}
int RMQ(int x ,int y)
{
int K = (int)(Math.log((double)(y-x+1)) / Math.log(2.0));
int a = dp[x][K] , b = dp[y-pow[K]+1][K];
if(R[a] < R[b]) return a;
else return b;
}
void add_diredge(int u, int v, int c){
adj[u].add(new Edge(u,v,c));
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//Tarjan
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
FastScanner sc = new FastScanner();
PrintWriter pw = new PrintWriter(System.out);
//LCA lca=new LCA();
Tarjan tarjan=new Tarjan();
int t=sc.nextInt();
while (sc.hasNext()) {
int n=sc.nextInt();
int[]deg=new int[n+1];
//lca.init();
tarjan.init();
for(int i=1;i<=n-1;i++){
int a=sc.nextInt();
int b=sc.nextInt();
deg[b]++;
//lca.add_diredge(a, b, 1);
tarjan.add_diredge(a, b, 1);
}
int s=0;
for(int i=1;i<=n;i++){
if(deg[i]==0)s=i;
}
//lca.dfs(s, 0);
//lca.st();
int x=sc.nextInt();
int y=sc.nextInt();
tarjan.addquery(x, y);
tarjan.tarjan(s);
for(int i=0;i<tarjan.count;i++)
pw.println(tarjan.answer[i]);
//pw.println(lca.lca(x, y));
pw.flush();
}
}
}
class Tarjan{
int[]pre;
int maxn=10010;
ArrayList<Edge>[]adj;
ArrayList<Query>[]query;
int[]answer;
int[]ancestor;
int count;
boolean[]vis;
Tarjan(){
pre=new int[maxn];
ancestor=new int[maxn];
adj=new ArrayList[maxn];
for(int i=0;i<maxn;i++)adj[i]=new ArrayList<Edge>();
query=new ArrayList[maxn];
for(int i=0;i<maxn;i++)query[i]=new ArrayList<Query>();
vis=new boolean[maxn];
answer=new int[maxn];
}
void init(){
for(int i=0;i<maxn;i++)pre[i]=i;
for(int i=0;i<maxn;i++)adj[i].clear();
for(int i=0;i<maxn;i++)query[i].clear();
Arrays.fill(vis, false);
Arrays.fill(ancestor, 0);
count=0;
}
void addquery(int u,int v){
query[u].add(new Query(u,v,count));
query[v].add(new Query(v,u,count));
count++;
}
void tarjan(int u){
vis[u]=true;
ancestor[u]=u;
for(int i=0;i<adj[u].size();i++){
int v=adj[u].get(i).v;
if(!vis[v]){
tarjan(v);
union(u,v);
ancestor[find(u)]=u;
}
}
for(int i=0;i<query[u].size();i++){
int v=query[u].get(i).v;
int index=query[u].get(i).index;
if(vis[v]){
answer[index]=ancestor[find(v)];
}
}
}
void add_diredge(int u, int v, int c){
adj[u].add(new Edge(u,v,c));
}
void union(int a,int b){
int fa=find(a);
int fb=find(b);
if(fa!=fb){
pre[fa]=fb;
}
}
int find(int x){
if(pre[x]==x)return x;
int root=find(pre[x]);
return pre[x]=root;
}
}
class Query{
int u;
int v;
int index;
Query(int u,int v,int index){
this.u=u;
this.v=v;
this.index=index;
}
}
class Edge{
int u;
int v;
int w;
Edge(int u,int v,int w){
this.u=u;
this.v=v;
this.w=w;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//倍增
import java.io.*;
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
Redouble re=new Redouble();
while(sc.hasNext()){
int n=sc.nextInt();
int m=sc.nextInt();
re.init();
int[]deg=new int[n+1];
for(int i=0;i<m;i++){
int a=sc.nextInt();
int b=sc.nextInt();
int w=sc.nextInt();
String s=sc.next();
re.adj[a].add(new Edge(a,b,w));
re.adj[b].add(new Edge(b,a,w));
}
re.dfs(1);
int k=sc.nextInt();
for(int o=1;o<=k;o++){
int x=sc.nextInt();
int y=sc.nextInt();
int lca=re.lca(x, y);
pw.println(re.dis[x]+re.dis[y]-2*re.dis[lca]);
}
pw.flush();
}

}

}
class Redouble{
int maxn=100050; //顶点数
int maxm=20;//1<<17 ~1e5
int[][]anc;
ArrayList<Edge>adj[]; //邻接边
int[]deep; //深度
int[]fa; //父节点
int[]dis; //与根节点的距离
Redouble(){
anc=new int[maxn][maxm];
adj=new ArrayList[maxn];
for(int i=0;i<maxn;i++)adj[i]=new ArrayList<Edge>();
deep=new int[maxn];
fa=new int[maxn];
dis=new int[maxn];
}
void init(){
for(int i=0;i<maxn;i++)adj[i].clear();
for(int i=0;i<maxn;i++)Arrays.fill(anc[i], 0);
Arrays.fill(deep, 0);
}
void dfs(int x){ //注意使用前给根的父亲赋值
anc[x][0]=fa[x];
for(int i=1;i<maxm;i++) anc[x][i]=anc[anc[x][i-1]][i-1]; //维护2^i的父亲结点
for(int i=0;i<adj[x].size();i++){
Edge temp=adj[x].get(i);
if(temp.v!=fa[x]){
fa[temp.v]=x;
deep[temp.v]=deep[x]+1;
dis[temp.v]=dis[x]+temp.w;
dfs(temp.v);
}
}
}
int lca(int x,int y){
if(deep[x]<deep[y]){int t=x;x=y;y=t;} //x深度较深
for(int i=maxm-1;i>=0;i--){ //把x移动到y的同一深度
if(deep[y]<=deep[anc[x][i]]) x=anc[x][i];
}
if(x==y)return x;
for(int i=maxm-1;i>=0;i--){ //两点一起倍增直到父亲相同
if(anc[x][i]!=anc[y][i]){
x=anc[x][i];
y=anc[y][i];
}
}
return anc[x][0];
}
}
class Edge{
int u;
int v;
int w;
Edge(int u,int v,int w){
this.u=u;
this.v=v;
this.w=w;
}
}