CH Round #58
A:颜色问题
题目：http://ch.ezoj.tk/contest/CH%20Round%20%2358%20-%20OrzCC杯noip模拟赛day2/颜色问题
题解：算一下每个仆人到它的目的地的时间取max即可
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 1500000 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 1000000007 23 using namespace std; 24 inline int read() 25 { 26 int x=0,f=1;char ch=getchar(); 27 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 28 while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();} 29 return x*f; 30 } 31 int n,f[maxn],head[maxn]; 32 struct edge{int go,next;}e[maxn]; 33 int main() 34 { 35 freopen("input.txt","r",stdin); 36 freopen("output.txt","w",stdout); 37 n=read(); 38 for1(i,n) 39 { 40 int x=read(); 41 e[i].go=i;e[i].next=head[x];head[x]=i; 42 f[i]=inf; 43 } 44 for1(i,n) 45 { 46 int x=read(); 47 for(int j=head[x];j;j=e[j].next) 48 { 49 int y=e[j].go; 50 if(y>=i)f[y]=min(f[y],y-i+1);else f[y]=min(f[y],n-i+y+1); 51 } 52 } 53 int ans=1; 54 for1(i,n)ans=max(ans,f[e[i].go]); 55 printf("%d ",ans==inf?-1:ans); 56 return 0; 57 }
B：树的问题
题目：http://ch.ezoj.tk/contest/CH%20Round%20%2358%20-%20OrzCC杯noip模拟赛day2/树的问题
题解：如果x和y的LCA不是其中任意一个，那么答案显然是s[x]+s[y]，画一下图就知道
否则不妨设LCA(x,y)=x，则ans=n-（s[son[x]]-s[y]) 其中son[x]是 x 走向 y的第一个点，画一下图就可以知道。。。
而son[x]不能dfs求，只要把y倍增上去即可。需要思考一下。
具体看代码
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 300000 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 1000000007 23 using namespace std; 24 inline int read() 25 { 26 int x=0,f=1;char ch=getchar(); 27 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 28 while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();} 29 return x*f; 30 } 31 int n,m,head[maxn],tot,fa[maxn],s[maxn],f[maxn][25],dep[maxn]; 32 struct edge{int go,next;}e[2*maxn]; 33 inline void insert(int x,int y) 34 { 35 e[++tot].go=y;e[tot].next=head[x];head[x]=tot; 36 e[++tot].go=x;e[tot].next=head[y];head[y]=tot; 37 } 38 void dfs(int x) 39 { 40 s[x]=1; 41 for1(i,20) 42 if((1<<i)<=dep[x])f[x][i]=f[f[x][i-1]][i-1]; 43 else break; 44 for(int i=head[x],y;i;i=e[i].next) 45 if(!dep[y=e[i].go]) 46 { 47 dep[y]=dep[x]+1; 48 f[y][0]=x; 49 dfs(y); 50 s[x]+=s[y]; 51 } 52 } 53 bool lca(int x,int y) 54 { 55 int ans=0; 56 if(dep[x]<dep[y])swap(x,y); 57 int t=dep[x]-dep[y]; 58 for0(i,20) 59 if(t&(1<<i))x=f[x][i]; 60 return x==y; 61 } 62 int main() 63 { 64 freopen("input.txt","r",stdin); 65 freopen("output.txt","w",stdout); 66 n=read();m=read(); 67 for1(i,n-1)insert(read(),read()); 68 dep[1]=1; 69 dfs(1); 70 while(m--) 71 { 72 int x=read(),y=read(); 73 if(dep[x]>dep[y])swap(x,y); 74 if(!lca(x,y))printf("%d ",s[x]+s[y]); 75 else 76 { 77 int t=dep[y]-dep[x]-1,w=y; 78 for0(i,20)if(t&(1<<i))w=f[w][i]; 79 printf("%d ",n-(s[w]-s[y])); 80 } 81 } 82 return 0; 83 }