【算法总结】树相关

【点分治】

〖模板代码〗

 1 void getroot(int x,int fa)
 2 {
 3     sz[x]=1;mx[x]=0;
 4     for(int i=first[x];i;i=e[i].next)
 5     {
 6         int to=e[i].to;
 7         if(to==fa||vis[to])continue;
 8         getroot(to,x);
 9         sz[x]+=sz[to];
10         mx[x]=max(mx[x],sz[to]);
11     }
12     mx[x]=max(mx[x],sum-sz[x]);
13     if(mx[root]>mx[x])root=x;
14 }
15 void getdeep(int x,int fa)
16 {
17     d[++tot]=deep[x];
18     for(int i=first[x];i;i=e[i].next)
19     {
20         int to=e[i].to;
21         if(to==fa||vis[to])continue;
22         deep[to]=deep[x]+e[i].w;
23         getdeep(to,x);
24     }
25 }
26 int calc(int x)
27 {
28     tot=0;getdeep(x,-1);
29     sort(d+1,d+tot+1);
30     int ans=0,i=1,j=tot;
31     while(i<j)
32     {
33         if(d[i]+d[j]<=K)ans+=j-i,i++;
34         else j--;
35     }
36     return ans;
37 }
38 void dfs(int x)
39 {
40     deep[x]=0;vis[x]=true;ans+=calc(x);
41     for(int i=first[x];i;i=e[i].next)
42     {
43         int to=e[i].to;
44         if(vis[to])continue;
45         deep[to]=e[i].w;
46         ans-=calc(to);
47         sum=sz[to];root=0;
48         getroot(to,-1);dfs(root);
49     }
50 }
51 int main()
52 {
53     root=0;sum=n;mx[0]=inf;
54     getroot(1,-1);dfs(root);
55     printf("%d
",ans);
56 }

View Code

〖相关题目〗

1.【poj1741】Tree

题意：给定一棵n个点的有边权的树，给定数字k，求满足x到y距离≤k的无序点对(x,y)的个数。

分析：GXZlegendの博客

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 const int N=1e4+5;
 6 const int inf=0x3f3f3f3f;
 7 int n,K,cnt,x,y,w,root,sum,ans,tot;
 8 int sz[N],mx[N],first[N],deep[N],d[N];
 9 bool vis[N];
10 struct edge{int to,next,w;}e[N<<1];
11 int read()
12 {
13     int x=0,f=1;char c=getchar();
14     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
15     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
16     return x*f;
17 }
18 void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}
19 void getroot(int x,int fa)
20 {
21     sz[x]=1;mx[x]=0;
22     for(int i=first[x];i;i=e[i].next)
23     {
24         int to=e[i].to;
25         if(to==fa||vis[to])continue;
26         getroot(to,x);
27         sz[x]+=sz[to];
28         mx[x]=max(mx[x],sz[to]);
29     }
30     mx[x]=max(mx[x],sum-sz[x]);
31     if(mx[root]>mx[x])root=x;
32 }
33 void getdeep(int x,int fa)
34 {
35     d[++tot]=deep[x];
36     for(int i=first[x];i;i=e[i].next)
37     {
38         int to=e[i].to;
39         if(to==fa||vis[to])continue;
40         deep[to]=deep[x]+e[i].w;
41         getdeep(to,x);
42     }
43 }
44 int calc(int x)
45 {
46     tot=0;getdeep(x,-1);
47     sort(d+1,d+tot+1);
48     int ans=0,i=1,j=tot;
49     while(i<j)
50     {
51         if(d[i]+d[j]<=K)ans+=j-i,i++;
52         else j--;
53     }
54     return ans;
55 }
56 void dfs(int x)
57 {
58     deep[x]=0;vis[x]=true;ans+=calc(x);
59     for(int i=first[x];i;i=e[i].next)
60     {
61         int to=e[i].to;
62         if(vis[to])continue;
63         deep[to]=e[i].w;
64         ans-=calc(to);
65         sum=sz[to];root=0;
66         getroot(to,-1);dfs(root);
67     }
68 }
69 int main()
70 {
71     n=read();K=read();
72     while(n||K)
73     {
74         cnt=0;ans=0;
75         memset(first,0,sizeof(first));
76         memset(vis,0,sizeof(vis));
77         for(int i=1;i<n;i++)
78         {
79             x=read();y=read();w=read();
80             ins(x,y,w);ins(y,x,w);
81         }
82         root=0;sum=n;mx[0]=inf;
83         getroot(1,-1);dfs(root);
84         printf("%d
",ans);
85         n=read();K=read();
86     }
87     return 0;
88 }

View Code

2.【bzoj2152】聪聪可可

题意：给定一棵n个点的有边权的树，求满足x到y距离恰好是3的倍数的有序点对(x,y)的个数/有序点对总个数。

分析：点分治裸题

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 const int N=2e4+5;
 6 const int inf=0x3f3f3f3f;
 7 int n,cnt,x,y,w,root,sum,ans;
 8 int t[3],first[N],mx[N],sz[N],deep[N];
 9 bool vis[N];
10 struct edge{int to,next,w;}e[N<<1];
11 int read()
12 {
13     int x=0,f=1;char c=getchar();
14     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
15     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
16     return x*f;
17 }
18 void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}
19 void getroot(int x,int fa)
20 {
21     sz[x]=1;mx[x]=0;
22     for(int i=first[x];i;i=e[i].next)
23     {
24         int to=e[i].to;
25         if(to==fa||vis[to])continue;
26         getroot(to,x);
27         sz[x]+=sz[to];
28         mx[x]=max(mx[x],sz[to]);
29     }
30     mx[x]=max(mx[x],sum-sz[x]);
31     if(mx[root]>mx[x])root=x;
32 }
33 void getdeep(int x,int fa)
34 {
35     t[deep[x]]++;
36     for(int i=first[x];i;i=e[i].next)
37     {
38         int to=e[i].to;
39         if(to==fa||vis[to])continue;
40         deep[to]=(deep[x]+e[i].w)%3;
41         getdeep(to,x);
42     }
43 }
44 int calc(int x)
45 {
46     t[0]=t[1]=t[2]=0;getdeep(x,-1);
47     return t[1]*t[2]*2+t[0]*t[0];
48 }
49 void dfs(int x)
50 {
51     deep[x]=0;vis[x]=true;ans+=calc(x);
52     for(int i=first[x];i;i=e[i].next)
53     {
54         int to=e[i].to;
55         if(vis[to])continue;
56         deep[to]=e[i].w;
57         ans-=calc(to);
58         sum=sz[to];root=0;
59         getroot(to,-1);dfs(root);
60     }
61 }
62 int gcd(int a,int b){return !b?a:gcd(b,a%b);}
63 int main()
64 {
65     n=read();
66     for(int i=1;i<n;i++)
67     {
68         x=read();y=read();w=read()%3;
69         ins(x,y,w);ins(y,x,w);
70     }
71     root=0;sum=n;mx[0]=inf;
72     getroot(1,-1);dfs(root);
73     int g=gcd(ans,n*n);
74     printf("%d/%d
",ans/g,n*n/g);
75     return 0;
76 }

View Code

3.【bzoj2599】[IOI2011]Race

题意：给一棵树，每条边有权。求一条简单路径，权值和等于K，且边的数量最小。

分析：wxx_louisaの博客

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 const int N=2e5+5;
 6 const int inf=0x3f3f3f3f;
 7 int n,K,cnt,x,y,w,root,sum,ans,froot;
 8 int first[N],sz[N],deep[N],dis[N],t[N*5];
 9 bool vis[N];
10 struct edge{int to,next,w;}e[N<<1];
11 int read()
12 {
13     int x=0,f=1;char c=getchar();
14     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
15     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
16     return x*f;
17 }
18 void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}
19 void getroot(int x,int fa)
20 {
21     bool flag=true;sz[x]=1;
22     for(int i=first[x];i;i=e[i].next)
23     {
24         int to=e[i].to;
25         if(to==fa||vis[to])continue;
26         getroot(to,x);
27         sz[x]+=sz[to];
28         if(sz[to]>sum/2)flag=false;
29     }
30     if(sum-sz[x]>sum/2)flag=false;
31     if(flag)root=x,froot=fa;
32 }
33 void getdeep(int x,int fa)
34 {
35     if(dis[x]<=K)ans=min(ans,deep[x]+t[K-dis[x]]);
36     for(int i=first[x];i;i=e[i].next)
37     {
38         int to=e[i].to;
39         if(to==fa||vis[to])continue;
40         dis[to]=dis[x]+e[i].w;
41         deep[to]=deep[x]+1;
42         getdeep(to,x);
43     }
44 }
45 void check(int x,int fa,int flag)
46 {
47     if(dis[x]<=K)
48     {
49         if(flag)t[dis[x]]=min(t[dis[x]],deep[x]);
50         else t[dis[x]]=n;
51     }
52     for(int i=first[x];i;i=e[i].next)
53     {
54         int to=e[i].to;
55         if(to==fa||vis[to])continue;
56         check(to,x,flag);
57     }
58 }
59 void dfs(int x,int s,int fa)
60 {
61     vis[x]=true;dis[x]=deep[x]=0;t[0]=0;
62     for(int i=first[x];i;i=e[i].next)
63     {
64         int to=e[i].to;
65         if(vis[to])continue;
66         deep[to]=1;dis[to]=e[i].w;
67         getdeep(to,x);check(to,x,1);
68     }
69     for(int i=first[x];i;i=e[i].next)
70     {
71         int to=e[i].to;
72         if(vis[to])continue;
73         check(to,x,0);
74     }
75     for(int i=first[x];i;i=e[i].next)
76     {
77         int to=e[i].to;
78         if(vis[to])continue;
79         if(to==fa)sum=s-sz[x];
80         else sum=sz[to];
81         root=0;getroot(to,x);
82         dfs(root,sum,froot);
83     }
84 }
85 int main()
86 {
87     n=read();K=read();
88     for(int i=1;i<=K;i++)t[i]=n;
89     for(int i=1;i<n;i++)
90     {
91         x=read()+1;y=read()+1;w=read();
92         ins(x,y,w);ins(y,x,w);
93     }
94     root=0;sum=n;ans=n;
95     getroot(1,-1);dfs(root,n,froot);
96     if(ans==n)printf("-1
");
97     else printf("%d
",ans);
98     return 0;
99 }

View Code

4.【bzoj3697】采药人的路径

题意：给定一棵n个点的树，边权只有0或1。一条路径是合法的，要求路径上边权为0和1的边数量相等，且路径中有一个点（不包括起点和终点），满足起点到该点和该点到终点的路径上边权为0和1的边数量也相等。求一共可以选择多少种不同的路径。

分析：CQzhangyuの博客

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define LL long long
 5 using namespace std;
 6 const int N=1e5+5;
 7 const int base=1e5;
 8 const int inf=0x3f3f3f3f;
 9 int n,cnt,x,y,w,sum,root,d;
10 int first[N],sz[N],mx[N],dep[N];
11 int s[N<<1],f[N<<1][2],g[N<<1][2];
12 LL ans;
13 bool vis[N];
14 struct edge{int to,next,w;}e[N<<1];
15 int read()
16 {
17     int x=0,f=1;char c=getchar();
18     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
19     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
20     return x*f;
21 }
22 void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}
23 void getroot(int x,int fa)
24 {
25     sz[x]=1;mx[x]=0;
26     for(int i=first[x];i;i=e[i].next)
27     {
28         int to=e[i].to;
29         if(to==fa||vis[to])continue;
30         getroot(to,x);
31         sz[x]+=sz[to];
32         mx[x]=max(mx[x],sz[to]);
33     }
34     mx[x]=max(mx[x],sum-sz[x]);
35     if(mx[root]>mx[x])root=x;
36 }
37 void getdeep(int x,int fa)
38 {
39     d=max(d,max(dep[x],-dep[x]));
40     if(s[dep[x]+base])g[dep[x]+base][1]++;
41     else g[dep[x]+base][0]++;
42     s[dep[x]+base]++;
43     for(int i=first[x];i;i=e[i].next)
44     {
45         int to=e[i].to;
46         if(to==fa||vis[to])continue;
47         dep[to]=dep[x]+e[i].w;
48         getdeep(to,x);
49     }
50     s[dep[x]+base]--;
51 }
52 void dfs(int x)
53 {
54     vis[x]=true;int dd=0;
55     for(int i=first[x];i;i=e[i].next)
56     {
57         int to=e[i].to;
58         if(vis[to])continue;
59         dep[to]=e[i].w;d=0;
60         getdeep(to,x);dd=max(dd,d);
61         for(int j=base-d;j<=base+d;j++)
62             ans+=1ll*f[base*2-j][0]*g[j][1]+1ll*f[base*2-j][1]*g[j][0]+1ll*f[base*2-j][1]*g[j][1];
63         ans+=1ll*f[base][0]*g[base][0]+g[base][1];
64         for(int j=base-d;j<=base+d;j++)
65             f[j][0]+=g[j][0],f[j][1]+=g[j][1],g[j][0]=g[j][1]=0;
66     }
67     for(int i=base-dd;i<=base+dd;i++)f[i][0]=f[i][1]=0;
68     for(int i=first[x];i;i=e[i].next)
69     {
70         int to=e[i].to;
71         if(vis[to])continue;
72         root=0;sum=sz[to];
73         getroot(to,x);dfs(root);
74     }
75 }
76 int main()
77 {
78     n=read();
79     for(int i=1;i<n;i++)
80     {
81         x=read();y=read();w=read();
82         w=(w==0)?-1:1;ins(x,y,w);ins(y,x,w);
83     }
84     root=0;sum=n;mx[0]=inf;
85     getroot(1,-1);dfs(root);
86     printf("%lld
",ans);
87     return 0;
88 }

View Code

5.【Codecraft-18 and Codeforces Round #458】E. Palindromes in a Tree

题意：给定n个点的树，每个点有一个a~t的字母，一条路径回文当且仅当路径上的字母的某一个排列回文，求经过每个点的回文路径数。

分析：点分治+状压

 1 #include<cstdio>
 2 #include<algorithm> 
 3 #include<cstring>
 4 #define LL long long
 5 using namespace std;
 6 const int N=2e5+5;
 7 const int inf=0x3f3f3f3f;
 8 int n,cnt,x,y,root,sum;
 9 int id[N],first[N],sz[N],mx[N];
10 bool vis[N];
11 LL ans[N],mp[(1<<20)+5];
12 char s[N];
13 struct edge{int to,next;}e[N*2];
14 int read()
15 {
16     int x=0,f=1;char c=getchar();
17     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
18     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
19     return x*f;
20 }
21 int max(int a,int b){return a>b?a:b;}
22 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
23 void getroot(int x,int fa)
24 {
25     sz[x]=1;mx[x]=0;
26     for(int i=first[x];i;i=e[i].next)
27     {
28         int to=e[i].to;
29         if(to==fa||vis[to])continue;
30         getroot(to,x);
31         sz[x]+=sz[to];
32         mx[x]=max(mx[x],sz[to]);
33     }
34     mx[x]=max(mx[x],sum-sz[x]);
35     if(mx[root]>mx[x])root=x;
36 }
37 void getway(int x,int fa,int val,int k)
38 {
39     val^=id[x];mp[val]+=k;
40     for(int i=first[x];i;i=e[i].next)
41     {
42         int to=e[i].to;
43         if(to==fa||vis[to])continue;
44         getway(to,x,val,k);
45     }
46 }
47 LL check(int x,int fa,int val)
48 {
49     val^=id[x];LL num=mp[val];
50     for(int i=0;i<20;i++)num+=mp[(1<<i)^val];
51     for(int i=first[x];i;i=e[i].next)
52     {
53         int to=e[i].to;
54         if(to==fa||vis[to])continue;
55         num+=check(to,x,val);
56     }
57     ans[x]+=num;return num;
58 }
59 void solve(int x)
60 {
61     vis[x]=true;getway(x,-1,0,1);
62     LL num=mp[0];
63     for(int i=0;i<20;i++)num+=mp[1<<i];
64     for(int i=first[x];i;i=e[i].next)
65     {
66         int to=e[i].to;
67         if(vis[to])continue;
68         getway(to,x,id[x],-1);
69         num+=check(to,x,0);
70         getway(to,x,id[x],1);
71     }
72     ans[x]+=num/2;getway(x,-1,0,-1);
73     for(int i=first[x];i;i=e[i].next)
74     {
75         int to=e[i].to;
76         if(vis[to])continue;
77         sum=sz[to];root=0;
78         getroot(to,-1);solve(root);
79     }
80 }
81 int main()
82 {
83     n=read();
84     for(int i=1;i<n;i++)x=read(),y=read(),ins(x,y),ins(y,x);
85     scanf("%s",s+1);
86     for(int i=1;i<=n;i++)id[i]=1<<(s[i]-'a');
87     sum=n;mx[0]=inf;getroot(1,-1);solve(root);
88     for(int i=1;i<=n;i++)printf("%lld ",ans[i]+1);
89     return 0;
90 }

View Code

【Link-Cut Tree】

〖相关资料〗

《动态树之link-cut tree》

〖模板代码〗

 1 struct LCT
 2 {
 3     int c[N][2],fa[N],sum[N],val[N];
 4     bool rev[N];
 5     bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
 6     void update(int x){sum[x]=sum[c[x][0]]+sum[c[x][1]]+val[x];}
 7     void flip(int x){swap(c[x][0],c[x][1]);rev[x]^=1;}
 8     void down(int x){if(rev[x])flip(c[x][0]),flip(c[x][1]),rev[x]=0;}
 9     void rotate(int x)
10     {
11         int y=fa[x],z=fa[y],l,r;
12         if(c[y][0]==x)l=0;else l=1;r=l^1;
13         if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
14         fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
15         c[y][l]=c[x][r];c[x][r]=y;
16         update(y);update(x);
17     }
18     void relax(int x){if(!isroot(x))relax(fa[x]);down(x);}
19     void splay(int x)
20     {
21         relax(x);
22         while(!isroot(x))
23         {
24             int y=fa[x],z=fa[y];
25             if(!isroot(y))
26             {
27                 if((c[y][0]==x)^(c[z][0]==y))rotate(x);
28                 else rotate(y);
29             }
30             rotate(x);
31         }
32     }
33     void access(int x){int t=0;while(x)splay(x),c[x][1]=t,update(x),t=x,x=fa[x];}
34     void makeroot(int x){access(x);splay(x);flip(x);}
35     bool connected(int x,int y)
36     {
37         if(x==y)return true;
38         makeroot(x);access(y);splay(y);return fa[x]!=0;
39     }
40     void modify(int x,int v){splay(x);val[x]=v;update(x);}
41     void link(int x,int y){makeroot(x);fa[x]=y;}
42     void cut(int x,int y){makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0;update(y);}
43     int query(int x,int y){makeroot(x);access(y);splay(y);return sum[y];}
44 }T;

View Code

〖相关题目〗

1.【bzoj3282】Tree

题意：给定n个点以及每个点的权值，处理m个操作。０：询问从ｘ到ｙ的路径上的点的权值的xor和。保证ｘ到ｙ是联通的。１：连接ｘ到ｙ，若ｘ到y已经联通则无需连接。２：删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。３：将点Ｘ上的权值变成Ｙ。

分析：Link-Cut Tree裸题

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define LL long long
 5 using namespace std;
 6 const int N=3e5+5;
 7 int n,m,op,x,y;
 8 int read()
 9 {
10     int x=0,f=1;char c=getchar();
11     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
12     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
13     return x*f;
14 }
15 struct LCT
16 {
17     int c[N][2],fa[N],sum[N],val[N];
18     bool rev[N];
19     bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
20     void update(int x){sum[x]=sum[c[x][0]]^sum[c[x][1]]^val[x];}
21     void flip(int x){swap(c[x][0],c[x][1]);rev[x]^=1;}
22     void down(int x){if(rev[x])flip(c[x][0]),flip(c[x][1]),rev[x]=0;}
23     void rotate(int x)
24     {
25         int y=fa[x],z=fa[y],l,r;
26         if(c[y][0]==x)l=0;else l=1;r=l^1;
27         if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
28         fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
29         c[y][l]=c[x][r];c[x][r]=y;
30         update(y);update(x);
31     }
32     void relax(int x){if(!isroot(x))relax(fa[x]);down(x);}
33     void splay(int x)
34     {
35         relax(x);
36         while(!isroot(x))
37         {
38             int y=fa[x],z=fa[y];
39             if(!isroot(y))
40             {
41                 if((c[y][0]==x)^(c[z][0]==y))rotate(x);
42                 else rotate(y);
43             }
44             rotate(x);
45         }
46     }
47     void access(int x){int t=0;while(x){splay(x);c[x][1]=t;update(x);t=x;x=fa[x];}}
48     void makeroot(int x){access(x);splay(x);flip(x);}
49     void modify(int x,int v){splay(x);val[x]=v;update(x);}
50     void link(int x,int y){makeroot(x);fa[x]=y;}
51     void cut(int x,int y){makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0;update(y);}
52     int query(int x,int y){makeroot(x);access(y);splay(y);return sum[y];}
53 }T;
54 int main()
55 {
56     n=read();m=read();
57     for(int i=1;i<=n;i++)T.val[i]=T.sum[i]=read();
58     while(m--)
59     {
60         op=read();x=read();y=read();
61         if(op==0)printf("%d
",T.query(x,y));
62         if(op==1)T.link(x,y);
63         if(op==2)T.cut(x,y);
64         if(op==3)T.modify(x,y);
65     }
66     return 0;
67 }

View Code

2.【bzoj1180】[CROATIAN2009]OTOCI

题意：给定n个点以及每个点的权值，处理m个操作。详见题目。

分析：Link-Cut Tree裸题

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define LL long long
 5 using namespace std;
 6 const int N=3e4+5;
 7 int n,m,x,y;
 8 char s[10];
 9 int read()
10 {
11     int x=0,f=1;char c=getchar();
12     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
13     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
14     return x*f;
15 }
16 struct LCT
17 {
18     int c[N][2],fa[N],sum[N],val[N];
19     bool rev[N];
20     bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
21     void update(int x){sum[x]=sum[c[x][0]]+sum[c[x][1]]+val[x];}
22     void flip(int x){swap(c[x][0],c[x][1]);rev[x]^=1;}
23     void down(int x){if(rev[x])flip(c[x][0]),flip(c[x][1]),rev[x]=0;}
24     void rotate(int x)
25     {
26         int y=fa[x],z=fa[y],l,r;
27         if(c[y][0]==x)l=0;else l=1;r=l^1;
28         if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
29         fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
30         c[y][l]=c[x][r];c[x][r]=y;
31         update(y);update(x);
32     }
33     void relax(int x){if(!isroot(x))relax(fa[x]);down(x);}
34     void splay(int x)
35     {
36         relax(x);
37         while(!isroot(x))
38         {
39             int y=fa[x],z=fa[y];
40             if(!isroot(y))
41             {
42                 if((c[y][0]==x)^(c[z][0]==y))rotate(x);
43                 else rotate(y);
44             }
45             rotate(x);
46         }
47     }
48     void access(int x){int t=0;while(x)splay(x),c[x][1]=t,update(x),t=x,x=fa[x];}
49     void makeroot(int x){access(x);splay(x);flip(x);}
50     bool connected(int x,int y)
51     {
52         if(x==y)return true;
53         makeroot(x);access(y);splay(y);return fa[x]!=0;
54     }
55     void modify(int x,int v){splay(x);val[x]=v;update(x);}
56     void link(int x,int y){makeroot(x);fa[x]=y;}
57     void cut(int x,int y){makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0;update(y);}
58     int query(int x,int y){makeroot(x);access(y);splay(y);return sum[y];}
59 }T;
60 int main()
61 {
62     n=read();
63     for(int i=1;i<=n;i++)T.sum[i]=T.val[i]=read();
64     m=read();
65     while(m--)
66     {
67         scanf("%s",s);x=read();y=read();
68         if(s[0]=='b')
69         {
70             if(T.connected(x,y))printf("no
");
71             else printf("yes
"),T.link(x,y);
72         }
73         if(s[0]=='p')T.modify(x,y);
74         if(s[0]=='e')
75         {
76             if(T.connected(x,y))printf("%d
",T.query(x,y));
77             else printf("impossible
");
78         }
79     }
80     return 0;
81 }

View Code

3.【bzoj2759】一个动态树好题

题意：有n个x[1..n]和n个等式组成的同余方程组：x[i]=k[i]*x[p[i]]+b[i] mod 10007。要应付Q个事务，每个是两种情况之一：一、询问当前x[a]的解，无解输出-1，多解输出-2，否则输出x[a]；二、修改一个等式 C a k[a] p[a] b[a]。

分析：PoPoQQQの博客

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define LL long long
  5 using namespace std;
  6 const int N=3e4+5;
  7 const int mod=1e4+7;
  8 int n,m,id,k,p,b;
  9 char op[2];
 10 int read()
 11 {
 12     int x=0,f=1;char c=getchar();
 13     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 14     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 15     return x*f;
 16 }
 17 struct data
 18 {
 19     int k,b;
 20     data(){k=1;b=0;}
 21     int calc(int x){return (k*x+b)%mod;}
 22 };
 23 data operator + (data a,data b)
 24 {
 25     data c;
 26     c.k=a.k*b.k%mod;
 27     c.b=(b.k*a.b%mod+b.b)%mod;
 28     return c;
 29 }
 30 int exgcd(int a,int b,int& x,int& y)
 31 {
 32     if(!b){x=1;y=0;return a;}
 33     int ans=exgcd(b,a%b,x,y);
 34     int tmp=x;x=y;y=tmp-a/b*y;
 35     return ans;
 36 }
 37 struct LCT
 38 {
 39     int c[N][2],fa[N],sfa[N];
 40     bool ins[N],vis[N];
 41     data val[N],sum[N];
 42     bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
 43     void update(int x){sum[x]=sum[c[x][0]]+val[x]+sum[c[x][1]];}
 44     void dfs(int x)
 45     {
 46         ins[x]=vis[x]=true;int to=fa[x];
 47         if(ins[to])fa[x]=0,sfa[x]=to;
 48         if(!vis[to])dfs(to);ins[x]=false;
 49     }
 50     void init(int n)
 51     {
 52         int k,b;
 53         for(int i=1;i<=n;i++)
 54         {
 55             k=read();fa[i]=read();b=read();
 56             data tmp;tmp.k=k;tmp.b=b;
 57             val[i]=sum[i]=tmp;
 58         }
 59         for(int i=1;i<=n;i++)if(!vis[i])dfs(i);
 60     }
 61     void rotate(int x)
 62     {
 63         int y=fa[x],z=fa[y],l,r;
 64         if(c[y][0]==x)l=0;else l=1;r=l^1;
 65         if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
 66         fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
 67         c[y][l]=c[x][r];c[x][r]=y;
 68         update(y);update(x);
 69     }
 70     void splay(int x)
 71     {
 72         while(!isroot(x))
 73         {
 74             int y=fa[x],z=fa[y];
 75             if(!isroot(y))
 76             {
 77                 if((c[y][0]==x)^(c[z][0]==y))rotate(x);
 78                 else rotate(y);
 79             }
 80             rotate(x);
 81         }
 82     }
 83     void access(int x){int t=0;while(x)splay(x),c[x][1]=t,update(x),t=x,x=fa[x];}
 84     int findroot(int x)
 85     {
 86         access(x);splay(x);
 87         int t=x;while(c[t][0])t=c[t][0];
 88         splay(t);return t;
 89     }
 90     int query(int x)
 91     {
 92         access(x);splay(x);data v1=sum[x];
 93         int rt=findroot(x),sf=sfa[rt];
 94         access(sf);splay(sf);data v2=sum[sf];
 95         if(v2.k==0)return v1.calc(v2.b);
 96         if(v2.k==1)return v2.b?-1:-2;
 97         int xx,yy;exgcd(v2.k-1,mod,xx,yy);
 98 //        return v1.calc((mod-xx)%mod*v2.b%mod);
 99         return v1.calc((xx%mod+mod)%mod*(((mod-v2.b)%mod+mod)%mod)%mod);
100     }
101     void cut(int x){access(x);splay(x);fa[c[x][0]]=0;c[x][0]=0;update(x);}
102     void link(int x,int f){access(x);splay(x);fa[x]=f;}
103     bool oncircle(int x,int rt)
104     {
105         int sf=sfa[rt];
106         if(x==sf)return true;
107         access(sf);splay(sf);splay(x);
108         return !isroot(sf);
109     }
110     void change(int x,int f,int k,int b)
111     {
112         access(x);splay(x);
113         data tmp;tmp.k=k;tmp.b=b;
114         val[x]=tmp;update(x);
115         int rt=findroot(x);
116         if(x==rt)
117         {
118             int rf=findroot(f);
119             if(rt==rf)sfa[x]=f;
120             else sfa[x]=0,link(x,f);
121         }
122         else
123         {
124             if(oncircle(x,rt))
125             {
126                 cut(x);link(rt,sfa[rt]);sfa[rt]=0;
127                 int rf=findroot(f);
128                 if(x==rf)sfa[x]=f;
129                 else link(x,f);
130             }
131             else
132             {
133                 cut(x);int rf=findroot(f);
134                 if(x==rf)sfa[x]=f;
135                 else link(x,f);
136             }
137         }
138     }
139 }lct;
140 int main()
141 {
142     n=read();lct.init(n);
143     m=read();
144     while(m--)
145     {
146         scanf("%s",op);id=read();
147         if(op[0]=='A')printf("%d
",lct.query(id));
148         else k=read(),p=read(),b=read(),lct.change(id,p,k,b);
149     }
150     return 0;
151 }

View Code

4.【bzoj4530】[Bjoi2014]大融合

题意：给定n个点，逐条加边，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。随着边的添加，动态的回答对于某些边的负载的询问。

分析：GXZlegendの博客

 1 #include<cstdio>
 2 #include<algorithm> 
 3 #include<cstring>
 4 #define LL long long
 5 using namespace std;
 6 const int N=1e5+5;
 7 int n,m,x,y;
 8 char op[2];
 9 int read()
10 {
11     int x=0,f=1;char c=getchar();
12     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
13     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
14     return x*f;
15 }
16 struct LCT
17 {
18     int c[N][2],fa[N],sum[N],val[N];
19     bool rev[N];
20     bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
21     void update(int x){sum[x]=sum[c[x][0]]+sum[c[x][1]]+val[x]+1;}
22     void flip(int x){swap(c[x][0],c[x][1]);rev[x]^=1;}
23     void down(int x){if(rev[x])flip(c[x][0]),flip(c[x][1]),rev[x]=0;}
24     void rotate(int x)
25     {
26         int y=fa[x],z=fa[y],l,r;
27         if(c[y][0]==x)l=0;else l=1;r=l^1;
28         if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
29         fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
30         c[y][l]=c[x][r];c[x][r]=y;
31         update(y);update(x);
32     }
33     void relax(int x){if(!isroot(x))relax(fa[x]);down(x);}
34     void splay(int x)
35     {
36         relax(x);
37         while(!isroot(x))
38         {
39             int y=fa[x],z=fa[y];
40             if(!isroot(y))
41             {
42                 if((c[y][0]==x)^(c[z][0]==y))rotate(x);
43                 else rotate(y);
44             }
45             rotate(x);
46         }
47     }
48     void access(int x)
49     {
50         int t=0;
51         while(x)
52         {
53             splay(x);val[x]+=sum[c[x][1]]-sum[t];
54             c[x][1]=t;update(x);t=x;x=fa[x];
55         }
56     }
57     void makeroot(int x){access(x);splay(x);flip(x);}
58     void link(int x,int y)
59     {
60         makeroot(x);makeroot(y);
61         fa[x]=y;val[y]+=sum[x];update(y);
62     }
63 }T;
64 int main()
65 {
66     n=read();m=read();
67     for(int i=1;i<=n;i++)T.sum[i]=1;
68     while(m--)
69     {
70         scanf("%s",op);
71         x=read();y=read();
72         if(op[0]=='A')T.link(x,y);
73         else 
74         {
75             T.makeroot(x);T.makeroot(y);
76             printf("%lld
",1ll*T.sum[x]*(T.sum[y]-T.sum[x]));
77         }
78     }
79     return 0;
80 }

View Code

5.【bzoj3779】重组病毒

题意：见原题

分析：Zsnuoの博客

  1 #include<cstdio>
  2 #include<algorithm> 
  3 #include<cstring>
  4 #define LL long long
  5 #define lc(x) x<<1
  6 #define rc(x) x<<1|1
  7 using namespace std;
  8 const int N=1e5+5;
  9 int n,m,x,y,cnt,dfn,rt=1,first[N];
 10 int deep[N],in[N],out[N],fa[N][18];
 11 char op[15];
 12 int read()
 13 {
 14     int x=0,f=1;char c=getchar();
 15     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 16     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 17     return x*f;
 18 }
 19 struct edge{int to,next;}e[N<<1];
 20 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
 21 struct SGT
 22 {
 23     int l[N*4],r[N*4];
 24     LL sum[N*4],tag[N*4];
 25     void build(int x,int L,int R)
 26     {
 27         l[x]=L;r[x]=R;if(L==R)return;
 28         int mid=(L+R)>>1;
 29         build(lc(x),L,mid);build(rc(x),mid+1,R);
 30     }
 31     void up(int x){sum[x]=sum[lc(x)]+sum[rc(x)];}
 32     void qadd(int x,LL w){tag[x]+=w;sum[x]+=w*(r[x]-l[x]+1);}
 33     void down(int x)
 34     {
 35         if(!tag[x])return;
 36         qadd(lc(x),tag[x]);qadd(rc(x),tag[x]);
 37         tag[x]=0;
 38     }
 39     void add(int x,int L,int R,LL w)
 40     {
 41         if(L<=l[x]&&r[x]<=R){qadd(x,w);return;}
 42         down(x);int mid=(l[x]+r[x])>>1;
 43         if(L<=mid)add(lc(x),L,R,w);
 44         if(R>mid)add(rc(x),L,R,w);
 45         up(x);
 46     }
 47     LL query(int x,int L,int R)
 48     {
 49         if(L<=l[x]&&r[x]<=R)return sum[x];
 50         down(x);LL ans=0;
 51         int mid=(l[x]+r[x])>>1;
 52         if(L<=mid)ans+=query(lc(x),L,R);
 53         if(R>mid)ans+=query(rc(x),L,R);
 54         return ans;
 55     }
 56 }sgt;
 57 int find(int x,int y)
 58 {
 59     int d=deep[y]-deep[x]-1;
 60     for(int i=16;i>=0;i--)
 61         if(d&(1<<i))y=fa[y][i];
 62     return y;
 63 }
 64 void addson(int x,LL w)
 65 {
 66     if(x==rt)sgt.add(1,1,n,w);
 67     else if(in[rt]>=in[x]&&out[rt]<=out[x])
 68     {
 69         int t=find(x,rt);
 70         if(in[t]>1)sgt.add(1,1,in[t]-1,w);
 71         if(out[t]<n)sgt.add(1,out[t]+1,n,w);
 72     }
 73     else sgt.add(1,in[x],out[x],w);
 74 }
 75 struct LCT
 76 {
 77     int c[N][2],fa[N],in[N],out[N];
 78     bool rev[N];
 79     bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
 80     void flip(int x){swap(c[x][0],c[x][1]);rev[x]^=1;}
 81     void down(int x){if(rev[x])flip(c[x][0]),flip(c[x][1]),rev[x]=0;}
 82     void rotate(int x)
 83     {
 84         int y=fa[x],z=fa[y],l,r;
 85         if(c[y][0]==x)l=0;else l=1;r=l^1;
 86         if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
 87         fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
 88         c[y][l]=c[x][r];c[x][r]=y;
 89     }
 90     void relax(int x){if(!isroot(x))relax(fa[x]);down(x);}
 91     void splay(int x)
 92     {
 93         relax(x);
 94         while(!isroot(x))
 95         {
 96             int y=fa[x],z=fa[y];
 97             if(!isroot(y))
 98             {
 99                 if((c[y][0]==x)^(c[z][0]==y))rotate(x);
100                 else rotate(y);
101             }
102             rotate(x);
103         }
104     }
105     int top(int x){down(x);while(c[x][0])x=c[x][0],down(x);return x;}
106     void access(int x)
107     {
108         int t=0;
109         while(x)
110         {
111             splay(x);
112             if(c[x][1])addson(top(c[x][1]),1);
113             if(t)addson(top(t),-1);
114             c[x][1]=t;t=x;x=fa[x];
115         }
116     }
117     void makeroot(int x){splay(x);rt=x;flip(x);}
118 }lct;
119 void dfs(int x)
120 {
121     in[x]=++dfn;
122     sgt.add(1,in[x],in[x],deep[x]);
123     for(int i=1;(1<<i)<=deep[x];i++)
124         fa[x][i]=fa[fa[x][i-1]][i-1];
125     for(int i=first[x];i;i=e[i].next)
126     {
127         int to=e[i].to;
128         if(to==fa[x][0])continue;
129         fa[to][0]=lct.fa[to]=x;
130         deep[to]=deep[x]+1;dfs(to);
131     }
132     out[x]=dfn;
133 }
134 double request(int x)
135 {
136     if(x==rt)return 1.0*sgt.query(1,1,n)/n;
137     if(in[rt]>=in[x]&&out[rt]<=out[x])
138     {
139         int t=find(x,rt);LL sum=0;
140         if(in[t]>1)sum+=sgt.query(1,1,in[t]-1);
141         if(out[t]<n)sum+=sgt.query(1,out[t]+1,n);
142         return 1.0*sum/(n-(out[t]-in[t]+1));
143     }
144     return 1.0*sgt.query(1,in[x],out[x])/(out[x]-in[x]+1);
145 }
146 int main()
147 {
148     n=read();m=read();
149     for(int i=1;i<n;i++)x=read(),y=read(),ins(x,y),ins(y,x);
150     sgt.build(1,1,n);deep[1]=1;dfs(1);
151     while(m--)
152     {
153         scanf("%s",op);x=read();
154         if(op[2]=='Q')printf("%.10lf
",request(x));
155         else
156         {
157             lct.access(x);
158             if(op[2]=='C')lct.makeroot(x);
159         }
160     }
161     return 0;
162 }

View Code

6.【bzoj4764】弹飞大爷

题意：见原题

分析：Zsnuoの博客

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int N=200050;
  6 int n,m,t,u,v,a[N],hl[N],hr[N],st[N];
  7 struct node{int fa,c[2],s;bool rev;}tr[5*N];
  8 int read()
  9 {
 10     int x=0,f=1;char c=getchar();
 11     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 12     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 13     return x*f;
 14 }
 15 bool isroot(int k){return !k||!tr[k].fa||(tr[tr[k].fa].c[0]!=k&&tr[tr[k].fa].c[1]!=k);}
 16 void up(int k){tr[k].s=tr[tr[k].c[0]].s+tr[tr[k].c[1]].s+1;}
 17 void down(int k)
 18 {
 19     int l=tr[k].c[0],r=tr[k].c[1];
 20     if(tr[k].rev)
 21     {
 22         tr[k].rev^=1;tr[l].rev^=1;tr[r].rev^=1;
 23         swap(tr[k].c[0],tr[k].c[1]);
 24     }
 25     if(l)hl[l]=hl[k],hr[l]=hr[k];
 26     if(r)hl[r]=hl[k],hr[r]=hr[k];
 27 }
 28 void rotate(int x)
 29 {
 30     int y=tr[x].fa,z=tr[y].fa,l,r;
 31     if(tr[y].c[0]==x)l=0;else l=1;r=l^1;
 32     if(!isroot(y)){if(tr[z].c[0]==y)tr[z].c[0]=x;else tr[z].c[1]=x;}
 33     tr[x].fa=z;tr[y].fa=x;tr[tr[x].c[r]].fa=y;
 34     tr[y].c[l]=tr[x].c[r];tr[x].c[r]=y;
 35     up(y);up(x);
 36 }
 37 void splay(int x)
 38 {
 39     int top=0;st[++top]=x;
 40     for(int i=x;!isroot(i);i=tr[i].fa)st[++top]=tr[i].fa;
 41     for(int i=top;i;i--)down(st[i]);
 42     while(!isroot(x))
 43     {
 44         int y=tr[x].fa,z=tr[y].fa;
 45         if(!isroot(y))
 46         {
 47             if((tr[y].c[0]==x)^(tr[z].c[0]==y))rotate(x);
 48             else rotate(y);
 49         }
 50         rotate(x);
 51     }
 52 }
 53 void acs(int x)
 54 {
 55     int t=0;
 56     while(x){splay(x);tr[x].c[1]=t;up(x);t=x;x=tr[x].fa;}
 57 }
 58 void mkroot(int x){acs(x);splay(x);tr[x].rev^=1;}
 59 int find(int x){acs(x);splay(x);while(tr[x].c[0])x=tr[x].c[0];return x;}
 60 void link(int x,int y){mkroot(x);tr[x].fa=y;acs(x);splay(x);}
 61 void cut(int x,int y)
 62 {
 63     mkroot(x);acs(y);splay(y);
 64     tr[x].fa=tr[y].c[0]=0;up(y);
 65     hl[x]=hr[x]=hl[y]=hr[y]=0;
 66 }
 67 void xlink(int x,int y)
 68 {
 69     if(find(x)==find(y))hl[y]=x,hr[y]=y;
 70     else link(x,y);
 71 }
 72 void xcut(int x,int y)
 73 {
 74     acs(x);splay(x);int li=hl[x],ri=hr[x];
 75     if(hl[x]==x&&hr[x]==y)hl[x]=hl[y]=hr[x]=hr[y]=0;
 76     else
 77     {
 78         cut(x,y);
 79         if(li&&ri)xlink(li,ri);//划重点！xlink而不是link。
 80     }
 81 }
 82 int query(int x)
 83 {
 84     mkroot(n+1);acs(x);splay(x);
 85     if(hl[x]&&hr[x])return -1;
 86     return tr[x].s-1;
 87 }
 88 int main()
 89 {
 90     n=read();m=read();
 91     for(int i=1;i<=n+1;i++)tr[i].s=1;
 92     for(int i=1;i<=n;i++)
 93     {
 94         a[i]=read();
 95         if(i+a[i]<=0||i+a[i]>n)link(i,n+1);
 96         else xlink(i,i+a[i]);
 97     }
 98     while(m--)
 99     {
100         t=read();
101         if(t==1)u=read(),printf("%d
",query(u));
102         else
103         {
104             u=read();v=read();
105             if(u+a[u]<=0||u+a[u]>n)cut(u,n+1);
106             else xcut(u,u+a[u]);
107             if(u+v<=0||u+v>n)link(u,n+1);
108             else xlink(u,u+v);
109             a[u]=v;
110         }
111     }
112     return 0;
113 }

View Code

7.【bzoj2002】弹飞绵羊

题意：见原题

分析：Zsnuoの博客

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=200050;
 6 int n,m,c[N][2],next[N],fa[N],size[N],st[N];
 7 bool rev[N];
 8 int read()
 9 {
10     int x=0,f=1;char c=getchar();
11     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
12     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
13     return x*f;
14 }
15 bool isroot(int k){return c[fa[k]][0]!=k&&c[fa[k]][1]!=k;}
16 void up(int x){size[x]=size[c[x][0]]+size[c[x][1]]+1;}
17 void down(int x)
18 {
19     int l=c[x][0],r=c[x][1];
20     if(rev[x]){rev[x]^=1;rev[l]^=1;rev[r]^=1;swap(c[x][0],c[x][1]);}
21 }
22 void rotate(int x)
23 {
24     int y=fa[x],z=fa[y],l,r;
25     if(c[y][0]==x)l=0;else l=1;r=l^1;
26     if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
27     fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
28     c[y][l]=c[x][r];c[x][r]=y;
29     up(y);up(x);
30 }
31 void splay(int x)
32 {
33     int top=0;st[++top]=x;
34     for(int i=x;!isroot(i);i=fa[i])st[++top]=fa[i];
35     for(int i=top;i;i--)down(st[i]);
36     while(!isroot(x))
37     {
38         int y=fa[x],z=fa[y];
39         if(!isroot(y))
40         {
41             if((c[y][0]==x)^(c[z][0]==y))rotate(x);
42             else rotate(y);
43         }
44         rotate(x);
45     }
46 }
47 void acs(int x)
48 {
49     int t=0;
50     while(x){splay(x);c[x][1]=t;t=x;x=fa[x];}
51 }
52 void mkroot(int x)
53 {
54     acs(x);splay(x);rev[x]^=1;
55 }
56 void link(int x,int y)
57 {
58     mkroot(x);fa[x]=y;splay(x);
59 }
60 void cut(int x,int y)
61 {
62     mkroot(x);acs(y);splay(y);c[y][0]=fa[x]=0;
63 }
64 int main()
65 {
66     n=read();
67     for(int i=1;i<=n;i++)
68     {
69         int x=read();
70         fa[i]=x+i;size[i]=1;
71         if(fa[i]>n+1)fa[i]=n+1;
72         next[i]=fa[i];
73     }
74     size[n+1]=1;
75     m=read();
76     while(m--)
77     {
78         int f=read();
79         if(f==1)
80         {
81             mkroot(n+1);
82             int x=read()+1;
83             acs(x);splay(x);printf("%d
",size[c[x][0]]);
84         }
85         else
86         {
87             int x=read()+1,y=read();
88             int t=min(n+1,x+y);
89             cut(x,next[x]);link(x,t);next[x]=t;
90         }
91     }
92     return 0;
93 }

View Code

8.【bzoj3669】[Noi2014]魔法森林

题意：见原题

分析：Zsnuoの博客

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 using namespace std;
 6 const int N=200050;
 7 const int inf=0x3f3f3f3f;
 8 int n,m,ans=inf,st[N];
 9 struct edge{int u,v,a,b;}e[N];
10 struct node{int fa,c[2],mx,val,p;bool rev;}tr[N];
11 int read()
12 {
13     int x=0,f=1;char c=getchar();
14     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
15     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
16     return x*f;
17 }
18 bool cmp(edge a,edge b){return a.a<b.a;}
19 int find(int k){return k==tr[k].p?k:tr[k].p=find(tr[k].p);}
20 bool isroot(int k){return tr[tr[k].fa].c[0]!=k&&tr[tr[k].fa].c[1]!=k;}
21 void up(int k)
22 {
23     int l=tr[k].c[0],r=tr[k].c[1];tr[k].mx=k;
24     if(tr[tr[l].mx].val>tr[tr[k].mx].val)tr[k].mx=tr[l].mx;
25     if(tr[tr[r].mx].val>tr[tr[k].mx].val)tr[k].mx=tr[r].mx;
26 }
27 void down(int k)
28 {
29     if(tr[k].rev)
30     {
31         int l=tr[k].c[0],r=tr[k].c[1];
32         tr[k].rev^=1;tr[l].rev^=1;tr[r].rev^=1;
33         swap(tr[k].c[0],tr[k].c[1]);
34     }
35 }
36 void rotate(int x)
37 {
38     int y=tr[x].fa,z=tr[y].fa,l,r;
39     if(tr[y].c[0]==x)l=0;else l=1;r=l^1;
40     if(!isroot(y)){if(tr[z].c[0]==y)tr[z].c[0]=x;else tr[z].c[1]=x;}
41     tr[x].fa=z;tr[y].fa=x;tr[tr[x].c[r]].fa=y;
42     tr[y].c[l]=tr[x].c[r];tr[x].c[r]=y;
43     up(y);up(x);
44 }
45 void splay(int x)
46 {
47     int top=0;st[++top]=x;
48     for(int i=x;!isroot(i);i=tr[i].fa)st[++top]=tr[i].fa;
49     for(int i=top;i;i--)down(st[i]);
50     while(!isroot(x))
51     {
52         int y=tr[x].fa,z=tr[y].fa;
53         if(!isroot(y))
54         {
55             if((tr[y].c[0]==x)^(tr[z].c[0]==y))rotate(x);
56             else rotate(y);
57         }
58         rotate(x);
59     }
60 }
61 void acs(int x){int t=0;while(x){splay(x);tr[x].c[1]=t;up(x);t=x;x=tr[x].fa;}}
62 void mkroot(int x){acs(x);splay(x);tr[x].rev^=1;}
63 void link(int x,int y){mkroot(x);tr[x].fa=y;splay(x);}
64 void cut(int x,int y){mkroot(x);acs(y);splay(y);tr[x].fa=tr[y].c[0]=0;}
65 int query(int x,int y){mkroot(x);acs(y);splay(y);return tr[y].mx;}
66 int main()
67 {
68     n=read();m=read();
69     for(int i=1;i<=n;i++)tr[i].p=i;
70     for(int i=1;i<=m;i++){e[i].u=read();e[i].v=read();e[i].a=read();e[i].b=read();}
71     sort(e+1,e+m+1,cmp);
72     for(int i=1;i<=m;i++)
73     {
74         int u=e[i].u,v=e[i].v,a=e[i].a,b=e[i].b;
75         if(find(u)==find(v))
76         {
77             int t=query(u,v);
78             if(tr[t].val>b){cut(t,e[t-n].u);cut(t,e[t-n].v);}
79             else{if(find(1)==find(n))ans=min(ans,a+tr[query(1,n)].val);continue;}
80         }
81         else tr[find(u)].p=find(v);
82         tr[i+n].val=b;tr[i+n].mx=i+n;link(u,i+n);link(v,i+n);
83         if(find(1)==find(n))ans=min(ans,a+tr[query(1,n)].val);
84     }
85     if(ans==inf)printf("-1");
86     else printf("%d
",ans);
87     return 0;
88 }

View Code

9.【bzoj2049】Cave洞穴勘测

题意：见原题

分析：Zsnuoの博客

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 const int N=10050;
 5 using namespace std;
 6 int n,m,a,b,c[N][2],fa[N],st[N];
 7 bool rev[N];
 8 int read()
 9 {
10     int x=0,f=1;char c=getchar();
11     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
12     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
13     return x*f;
14 }
15 bool isroot(int k){return c[fa[k]][0]!=k&&c[fa[k]][1]!=k;}
16 void down(int x)
17 {
18     int l=c[x][0],r=c[x][1];
19     if(rev[x]){rev[x]^=1;rev[l]^=1;rev[r]^=1;swap(c[x][0],c[x][1]);}
20 }
21 void rotate(int x)
22 {
23     int y=fa[x],z=fa[y],l,r;
24     if(c[y][0]==x)l=0;else l=1;r=l^1;
25     if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
26     fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
27     c[y][l]=c[x][r];c[x][r]=y;
28 }
29 void splay(int x)
30 {
31     int top=0;st[++top]=x;
32     for(int i=x;!isroot(i);i=fa[i])st[++top]=fa[i];
33     for(int i=top;i;i--)down(st[i]);
34     while(!isroot(x))
35     {
36         int y=fa[x],z=fa[y];
37         if(!isroot(y))
38         {
39             if((c[y][0]==x)^(c[z][0]==y))rotate(x);
40             else rotate(y);
41         }
42         rotate(x);
43     }
44 }
45 void acs(int x){int t=0; while(x){splay(x);c[x][1]=t;t=x;x=fa[x];} }
46 void mkroot(int x){acs(x);splay(x);rev[x]^=1;}
47 void link(int x,int y){mkroot(x);fa[x]=y;splay(x);}
48 void cut(int x,int y){mkroot(x);acs(y);splay(y);c[y][0]=fa[x]=0;}
49 int find(int x){acs(x);splay(x);while(c[x][0])x=c[x][0];return x;}
50 int main()
51 {
52     char s[15];
53     n=read();m=read();
54     while(m--)
55     {
56         scanf("%s",s);a=read();b=read();
57         if(s[0]=='Q')
58         {
59             if(find(a)!=find(b))printf("No
");
60             else printf("Yes
");
61         }
62         else if(s[0]=='C')link(a,b);
63         else cut(a,b);
64     }
65     return 0;
66 }

View Code

【虚树】

〖相关资料〗

《虚树详解＋例子分析＋模板》

〖相关题目〗

1.【bzoj2286】[Sdoi2011]消耗战

题意：给定n个点的带边权树，每次询问给定ki个特殊点，求隔离点1和特殊点的最小代价。

分析：ONION_CYCの博客

 1 #include<cstdio>
 2 #include<algorithm> 
 3 #include<cstring>
 4 #define LL long long
 5 using namespace std;
 6 const int N=250005;
 7 const int inf=0x3f3f3f3f;
 8 int n,m,x,y,w,tim,cnt,cntv;
 9 int a[N<<1],first[N],firstv[N],st[N]; 
10 int dfn[N],out[N],deep[N],fa[N][20];
11 LL val[N];
12 bool f[N];
13 struct edge{int to,next,w;}e[N<<1],ev[N<<1];
14 int read()
15 {
16     int x=0,f=1;char c=getchar();
17     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
18     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
19     return x*f;
20 }
21 void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}
22 void insv(int u,int v){ev[++cntv]=(edge){v,firstv[u],0};firstv[u]=cntv;}
23 void dfs(int x)
24 {
25     dfn[x]=++tim;
26     for(int i=1;(1<<i)<=deep[x];i++)
27         fa[x][i]=fa[fa[x][i-1]][i-1];
28     for(int i=first[x];i;i=e[i].next)
29     {
30         int to=e[i].to;
31         if(to==fa[x][0])continue;
32         fa[to][0]=x;
33         deep[to]=deep[x]+1;
34         val[to]=min(val[x],1ll*e[i].w);
35         dfs(to);
36     }
37     out[x]=tim;
38 }
39 int lca(int x,int y)
40 {
41     if(deep[x]<deep[y])swap(x,y);
42     int d=deep[x]-deep[y];
43     for(int i=0;(1<<i)<=d;i++)
44         if((1<<i)&d)x=fa[x][i];
45     if(x==y)return x;
46     for(int i=18;i>=0;i--)
47         if((1<<i)<=deep[x]&&fa[x][i]!=fa[y][i])
48             x=fa[x][i],y=fa[y][i];
49     return fa[x][0];
50 }
51 bool cmp(int a,int b){return dfn[a]<dfn[b];}
52 bool check(int x,int y){return dfn[x]<=out[y];}
53 LL dp(int x)
54 {
55     if(f[x])return val[x];LL sum=0;
56     for(int i=firstv[x];i;i=ev[i].next)sum+=dp(ev[i].to);
57     return min(val[x],sum);
58 }
59 void work()
60 {
61     int k=read(),tmp=k;
62     for(int i=1;i<=k;i++)a[i]=read(),f[a[i]]=true;
63     sort(a+1,a+k+1,cmp);
64     for(int i=1;i<tmp;i++)a[++k]=lca(a[i],a[i+1]);
65     sort(a+1,a+k+1,cmp);
66     k=unique(a+1,a+k+1)-a-1;
67     for(int i=1;i<=k;i++)firstv[a[i]]=0;
68     cntv=0;int top=0;
69     for(int i=1;i<=k;i++)
70     {
71         while(top&&!check(a[i],st[top]))top--;
72         if(top)insv(st[top],a[i]);
73         st[++top]=a[i];
74     }
75     printf("%lld
",dp(a[1]));
76     for(int i=1;i<=k;i++)f[a[i]]=false;
77 } 
78 int main()
79 {
80     n=read();
81     for(int i=1;i<n;i++)
82     {
83         x=read();y=read();w=read();
84         ins(x,y,w);ins(y,x,w);
85     }
86     val[1]=1e16;dfs(1);
87     m=read();
88     while(m--)work();
89     return 0;
90 }

View Code

2.【bzoj3572】[Hnoi2014]世界树

题意：给定n个点的树，m次询问，每次给定ki个特殊点，一个点会被最近的特殊点控制，询问每个特殊点控制多少点。

分析：hzwerの博客

  1 #include<cstdio>
  2 #include<algorithm> 
  3 #include<cstring>
  4 #define LL long long
  5 using namespace std;
  6 const int N=300005;
  7 int n,m,x,y,cnt,tim,top;
  8 int a[N],b[N],bel[N],first[N],st[N],rem[N],f[N];
  9 int size[N],dfn[N],out[N],deep[N],fa[N][20];
 10 struct edge{int to,next;}e[N<<1];
 11 int read()
 12 {
 13     int x=0,f=1;char c=getchar();
 14     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 15     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 16     return x*f;
 17 }
 18 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
 19 void dfs(int x)
 20 {
 21     dfn[x]=++tim;size[x]=1;
 22     for(int i=1;(1<<i)<=deep[x];i++)
 23         fa[x][i]=fa[fa[x][i-1]][i-1];
 24     for(int i=first[x];i;i=e[i].next)
 25     {
 26         int to=e[i].to;
 27         if(to==fa[x][0])continue;
 28         deep[to]=deep[x]+1;
 29         fa[to][0]=x;dfs(to);
 30         size[x]+=size[to];
 31     }
 32     out[x]=tim;
 33 }
 34 int lca(int x,int y)
 35 {
 36     if(deep[x]<deep[y])swap(x,y);
 37     int d=deep[x]-deep[y];
 38     for(int i=0;(1<<i)<=d;i++)
 39         if((1<<i)&d)x=fa[x][i];
 40     if(x==y)return x;
 41     for(int i=18;i>=0;i--)
 42         if((1<<i)<=deep[x]&&fa[x][i]!=fa[y][i])
 43             x=fa[x][i],y=fa[y][i];
 44     return fa[x][0];
 45 }
 46 bool cmp(int a,int b){return dfn[a]<dfn[b];}
 47 int dis(int a,int b){return deep[a]+deep[b]-2*deep[lca(a,b)];}
 48 bool check(int x,int y){return dfn[x]<=out[y];}
 49 void dfs1(int x)
 50 {
 51     rem[x]=size[x];
 52     for(int i=first[x];i;i=e[i].next)
 53     {
 54         int to=e[i].to;dfs1(to);
 55         if(!bel[to])continue;
 56         int d1=dis(x,bel[to]),d2=dis(x,bel[x]);
 57         if(!bel[x]||d1<d2||(d1==d2&&bel[to]<bel[x]))bel[x]=bel[to];
 58     }
 59 }
 60 void dfs2(int x)
 61 {
 62     for(int i=first[x];i;i=e[i].next)
 63     {
 64         int to=e[i].to;
 65         int d1=dis(to,bel[x]),d2=dis(to,bel[to]);
 66         if(!bel[to]||d1<d2||(d1==d2&&bel[x]<bel[to]))bel[to]=bel[x];
 67         dfs2(to);
 68     }
 69 }
 70 void solve(int a,int b)
 71 {
 72     int x=b,mid=b;
 73     for(int i=18;i>=0;i--)
 74         if(deep[fa[x][i]]>deep[a])x=fa[x][i];
 75     rem[a]-=size[x];
 76     if(bel[a]==bel[b])
 77     {
 78         f[bel[a]]+=size[x]-size[b];
 79         return;
 80     }
 81     for(int i=18;i>=0;i--)
 82     {
 83         int y=fa[mid][i];
 84         if(deep[y]<=deep[a])continue;
 85         int d1=dis(bel[a],y),d2=dis(bel[b],y);
 86         if(d2<d1||(d1==d2&&bel[b]<bel[a]))mid=y;
 87     }
 88     f[bel[a]]+=size[x]-size[mid];
 89     f[bel[b]]+=size[mid]-size[b];
 90 }
 91 void work()
 92 {
 93     int k=read(),tmp=k;
 94     for(int i=1;i<=k;i++)a[i]=b[i]=read();
 95     for(int i=1;i<=k;i++)bel[a[i]]=a[i];
 96     sort(a+1,a+k+1,cmp);
 97     for(int i=1;i<tmp;i++)a[++k]=lca(a[i],a[i+1]);
 98     a[++k]=1;sort(a+1,a+k+1,cmp);
 99     k=unique(a+1,a+k+1)-a-1;
100     cnt=top=0;
101     for(int i=1;i<=k;i++)first[a[i]]=0;
102     for(int i=1;i<=k;i++)
103     {
104         while(top&&!check(a[i],st[top]))top--;
105         if(top)ins(st[top],a[i]);
106         st[++top]=a[i];
107     }
108     dfs1(1);dfs2(1);
109     for(int i=1;i<=k;i++)
110         for(int j=first[a[i]];j;j=e[j].next)
111             solve(a[i],e[j].to);
112     for(int i=1;i<=k;i++)f[bel[a[i]]]+=rem[a[i]];
113     for(int i=1;i<=tmp;i++)printf("%d ",f[b[i]]);
114     printf("
");
115     for(int i=1;i<=k;i++)f[a[i]]=bel[a[i]]=0;
116 }
117 int main()
118 {
119     n=read();
120     for(int i=1;i<n;i++)
121     {
122         x=read();y=read();
123         ins(x,y);ins(y,x);
124     }
125     dfs(1);m=read();
126     while(m--)work();
127     return 0;
128 }

View Code