标签：memset dfs val logs tin 完全 lca 最大 can
这题是吴老师推荐的，于是我就去做了。
根据题意，在完成最大生成树后，对于树上从x到y的一条路径，求出最大的ck-cj(j
我一开始的想法是二分，记路径xy的中点是mid，路径ab的答案记为ans(a,b)，最大值为mx(a,b)，最小值为mn(a,b)，那么，ans(x,y)=max{ans(x,mid),ans(y,mid),mx(mid,y)-mn(x,mid)}。
但我忘记了一个问题，对于时间复杂度T(n)=2T(n/2)+logn，由主定理可知，解为T(n)=O(n)。换言之这并没有比暴力优越。
然而，正如同求路径上的最大最小值一样，我们可以通过倍增的方法把ans预处理出来，然后在O(logn)的时间内得到解。
具体说就是把一个点向上2^i的答案和一个点第2^i-1个祖先到i的答案都预处理出来。而预处理和最终计算答案的方法和上述的二分是完全一致的。
所以，我们可以通过O(n*logn)的时间完成预处理，再对与每个询问O(logn)地得到解。
时间复杂度O(n*logn+q*logn)。
1 #include 2 using namespace std;
3 template inline void read(tp& x)
4 {
5 x=0;
6 char tmp=getchar();bool key=0;
7 for(;!((tmp>=‘0‘&&tmp‘9‘)||tmp==‘-‘);) tmp=getchar();
8 if(tmp==‘-‘) key=1,tmp=getchar();
9 for(;tmp>=‘0‘&&tmp‘9‘;) x=(x1)+(x3)+tmp-‘0‘,tmp=getchar();
10 if(key) x=-x;
11 }
12 const int N=30010,M=50010,MAXPOS=15;
13 struct edge_for_buildtree{
14 int a,b,v;
15 bool operator const edge_for_buildtree& x)const
16 {
17 return v>x.v;
18 }
19 }ed[M];
20 struct edge_for_lca{
21 int la,b;
22 }con[N1];
23 int tot,fir[N];
24 inline void add(int from,int to)
25 {
26 con[++tot].la=fir[from];
27 con[tot].b=to;
28 fir[from]=tot;
29 }
30 int n,m,q,val[N],flag[N],anc[N][MAXPOS+5],mn[N][MAXPOS+5],mx[N][MAXPOS+5],deep[N];
31 int recu[N][MAXPOS+5],recd[N][MAXPOS+5];
32 inline void init()
33 {
34 memset(anc,0,sizeof anc);
35 memset(mn,0x3f,sizeof mn);
36 memset(mx,0,sizeof mx);
37 memset(fir,0,sizeof fir);
38 memset(recu,0,sizeof recu);
39 memset(recd,0,sizeof recd);
40 tot=0;
41 }
42 int get_flag(int pos)
43 {
44 return flag[pos]==pos? pos : flag[pos]=get_flag(flag[pos]);
45 }
46 inline void kruskal()
47 {
48 int x,y,ans=0,cnt=0;
49 sort(ed+1,ed+m+1);
50 for(register int i=1;ii;
51 for(register int i=1;ii)
52 {
53 x=ed[i].a;y=ed[i].b;
54 x=get_flag(x);y=get_flag(y);
55 if(x==y) continue;
56 add(ed[i].a,ed[i].b);
57 add(ed[i].b,ed[i].a);
58 ans+=ed[i].v;
59 flag[x]=y;
60 if(++cnt==n-1) break;
61 }
62 printf("%d\n",ans);
63 }
64 void dfs_init(int pos)
65 {
66 deep[pos]=deep[anc[pos][0]]+1;
67 mn[pos][0]=mx[pos][0]=val[pos];
68 recu[pos][0]=recd[pos][0]=0;
69 for(int i=1;ii)
70 {
71 anc[pos][i]=anc[anc[pos][i-1]][i-1];
72 mn[pos][i]=min(mn[pos][i-1],mn[anc[pos][i-1]][i-1]);
73 mx[pos][i]=max(mx[pos][i-1],mx[anc[pos][i-1]][i-1]);
74 recu[pos][i]=max(max(recu[pos][i-1],recu[anc[pos][i-1]][i-1]),mx[anc[pos][i-1]][i-1]-mn[pos][i-1]);
75 recd[pos][i]=max(max(recd[pos][i-1],recd[anc[pos][i-1]][i-1]),mx[pos][i-1]-mn[anc[pos][i-1]][i-1]);
76 if(anc[pos][i]==0) break;
77 }
78 for(int i=fir[pos];i;i=con[i].la)
79 {
80 if(con[i].b==anc[pos][0]) continue;
81 anc[con[i].b][0]=pos;
82 dfs_init(con[i].b);
83 }
84 }
85 inline int lca(int x,int y)
86 {
87 if(deep[x]deep[y]) swap(x,y);
88 for(int i=MAXPOS;i>=0;--i)
89 {
90 if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
91 }
92 if(x==y) return x;
93 for(int i=MAXPOS;i>=0;--i)
94 {
95 if(anc[x][i]!=anc[y][i])
96 x=anc[x][i],y=anc[y][i];
97 }
98 return anc[x][0];
99 }
100 inline int get_mn(int x,int y)//y is the ancestor of x
101 {
102 if(x==y) return val[x];
103 int res=val[x],len=deep[x]-deep[y]+1;
104 for(int i=MAXPOS;i>=0;--i)
105 {
106 if(len>=(1i))
107 res=min(res,mn[x][i]),x=anc[x][i],len-=(1i);
108 }
109 return res;
110 }
111 inline int get_mx(int x,int y)//y is the ancestor of x
112 {
113 if(x==y) return val[x];
114 int res=val[x],len=deep[x]-deep[y]+1;
115 for(int i=MAXPOS;i>=0;--i)
116 {
117 if(len>=(1i))
118 res=max(res,mx[x][i]),x=anc[x][i],len-=(1i);
119 }
120 return res;
121 }
122 inline int ask_mn(int x,int y,int lc)
123 {
124 return min(get_mn(x,lc),get_mn(y,lc));
125 }
126 inline int ask_mx(int x,int y,int lc)
127 {
128 return max(get_mx(x,lc),get_mx(y,lc));
129 }
130 inline int get_recu(int x,int y)//y is the ancestor of x
131 {
132 if(x==y) return 0;
133 int mnpre=1000000,res=0;
134 for(int i=MAXPOS;i>=0;i--)
135 {
136 if(deep[anc[x][i]]>=deep[y])
137 {
138 res=max(res,recu[x][i]);
139 res=max(res,mx[x][i]-mnpre);
140 mnpre=min(mnpre,mn[x][i]);
141 x=anc[x][i];
142 }
143 }
144 return res;
145 }
146 inline int get_recd(int x,int y)
147 {
148 if(x==y) return 0;
149 int mxpre=0,res=0;
150 for(int i=MAXPOS;i>=0;i--)
151 {
152 if(deep[anc[x][i]]>=deep[y])
153 {
154 res=max(res,recd[x][i]);
155 res=max(res,mxpre-mn[x][i]);
156 mxpre=max(mxpre,mx[x][i]);
157 x=anc[x][i];
158 }
159 }
160 return res;
161 }
162 inline int solve(int x,int y)
163 {
164 if(x==y) return 0;
165 if(anc[x][0]==y||anc[y][0]==x) return max(0,val[y]-val[x]);
166 int z=lca(x,y);
167 int res=max(get_recu(x,z),get_recd(y,z));
168 res=max(res,ask_mx(y,z,z)-ask_mn(x,z,z));
169 return res;
170 }
171 int main()
172 {
173 int x,y,v;
174 while(scanf("%d",&n)!=EOF)
175 {
176 init();
177 for(register int i=1;ii) read(val[i]);
178 read(m);
179 for(register int i=1;ii)
180 {
181 read(x);read(y);read(v);
182 ed[i]=(edge_for_buildtree){x,y,v};
183 }
184 kruskal();
185 dfs_init(1);
186 read(q);
187 for(;q--;)
188 {
189 read(x);read(y);
190 printf("%d\n",solve(x,y));
191 }
192 }
193 return 0;
194 }
小结：通常对于无修改的题目，这种看似无用的二分往往可以通过倍增来优化。
【做题】zoj3649 Social Net——倍增
标签：memset dfs val logs tin 完全 lca 最大 can
原文地址：http://www.cnblogs.com/cly-none/p/7749576.html