本文共 2133 字，大约阅读时间需要 7 分钟。
这道题是学点分治后打的练习题。一开始是看HZW的题解（）
然后就是明白思路就自己打了。然后锅+++++++；
一开始的那个更新答案，我的那个更新答案就直接放在深搜函数里了，导致在深搜中途父亲节点直接换了，集训室大佬hjj给我调了两个晚上，用对拍终于发现父亲节点更换了。然后本来以为AC，然后就WA了。
后来发现在每次清除mp数组的时候，进行深搜，但是这个深搜附带更新答案，所以在清除mp数组时，其实所有点已经进入mp了，这时候更新答案会使得两个在同一颗子树的端点更新答案。
所以还是HZW的打法好，深搜时不更新答案。我比较懒，直接在原来基础上传个标志算了。
这题从T改到RE，再从ＲＥ改到WA，看来还是不够熟练呀！
1 // Cease to struggle and you cease to live 2 #pragma comment(linker,"/STACK:102400000,102400000") 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std; 14 typedef long long ll; 15 const ll modd=1e6+3; 16 const ll inf=1e9; 17 const int N=1e5+9; 18 int h[N],siz[N],root,mx,top,all; 19 ll inv[1000000+10],val[N],dis[N],mp[1000005]; 20 bool vis[N]; 21 int n,cnt; 22 ll ans1,ans2; 23 ll k; 24 struct edge{ 25 int to,nex; 26 }e[N<<1]; 27 struct arr{ 28 ll len; 29 int id; 30 }tem[N]; 31 void add(int u,int v){ 32 e[++cnt]=(edge){v,h[u]}; 33 h[u]=cnt; 34 } 35 void getrt(int u,int fa){ 36 siz[u]=1; 37 int num=0; 38 for(int i=h[u];i;i=e[i].nex){ 39 int v=e[i].to; 40 if(vis[v] || v==fa ) continue; 41 getrt(v,u); 42 siz[u]+=siz[v]; 43 num=max(num,siz[v]); 44 } 45 num=max(num,all-siz[u]); 46 if(num u) swap(y,u); 53 if(y tem[i].id) mp[l]=tem[i].id; 72 } 73 } 74 void cal(int u){ 75 dis[u]=val[u]; 76 mp[(int)val[u]]=u; 77 for(int i=h[u];i;i=e[i].nex){ 78 int v=e[i].to; 79 if(vis[v]) continue; 80 dis[v]=val[v]; 81 top=0; 82 getdis(v,u,1); 83 savedis(u); 84 } 85 mp[(int)val[u]]=0; 86 for(int i=h[u];i;i=e[i].nex){ 87 int v=e[i].to; 88 if(vis[v]) continue; 89 dis[v]=val[v]; 90 top=0; 91 getdis(v,u,0); 92 for(int i=1;i<=top;++i){ 93 int l=(tem[i].len*val[u])%modd; 94 mp[l]=0; 95 } 96 } 97 98 99 }100 void dfs(int u){101 cal(u);102 vis[u]=1;103 for(int i=h[u];i;i=e[i].nex){104 int v=e[i].to;105 if(vis[v]) continue;106 all=siz[v];107 mx=0x3f3f3f3f;108 getrt(v,0);109 dfs(root);110 }111 }112 void init(){113 inv[1]=1;114 for(int i=2;i
转载于:https://www.cnblogs.com/xiaobuxie/p/10831239.html
