解题：ZJOI 2015 幻想乡战略游戏

神**所有点都爆int，我还以为我写出什么大锅了，不开long long见祖宗。。。

动态点分治利用点分树树高不超过log的性质，我们对每个点维护一个子树和，一个点分树子树和，一个点分树上父亲的子树和。修改直接爬点分树，查询在点分树上往答案较小的儿子上跳，如果儿子都不如自己优说明自己就是最优的

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int N=100005,inf=1e9;
  6 int n,c,T,t1,t2,t3,cnt,Cnt,sizz;
  7 int p[N],noww[2*N],goal[2*N],val[2*N];
  8 int siz[N],dep[N],far[N],imp[N],top[N],dis[N];
  9 int P[N],Noww[2*N],Goal[2*N],Val[2*N];
 10 int sze[N],maxx[N],vis[N],fer[N];
 11 long long sum[N],dst[N][2];
 12 void Link(int f,int t,int v)
 13 {
 14     noww[++cnt]=p[f],p[f]=cnt;
 15     goal[cnt]=t,val[cnt]=v;
 16     noww[++cnt]=p[t],p[t]=cnt;
 17     goal[cnt]=f,val[cnt]=v;
 18 }
 19 void Linka(int f,int t,int v)
 20 {
 21     Noww[++Cnt]=P[f],P[f]=Cnt;
 22     Goal[Cnt]=t,Val[Cnt]=v;
 23     Noww[++Cnt]=P[t],P[t]=Cnt;
 24     Goal[Cnt]=f,Val[Cnt]=v;
 25 }
 26 void DFS(int nde,int fth,int dth)
 27 {
 28     int tmp=0;
 29     siz[nde]=1,far[nde]=fth,dep[nde]=dth;
 30     for(int i=p[nde];i;i=noww[i])
 31         if(goal[i]!=fth)
 32         {
 33             dis[goal[i]]=dis[nde]+val[i];
 34             DFS(goal[i],nde,dth+1);
 35             siz[nde]+=siz[goal[i]];
 36             if(siz[goal[i]]>tmp)
 37                 tmp=siz[goal[i]],imp[nde]=goal[i];
 38         }
 39 }
 40 void Gettop(int nde,int tpp)
 41 {
 42     top[nde]=tpp;
 43     if(imp[nde])
 44     {
 45         Gettop(imp[nde],tpp);
 46         for(int i=p[nde];i;i=noww[i])
 47             if(goal[i]!=far[nde]&&goal[i]!=imp[nde])
 48                 Gettop(goal[i],goal[i]);
 49     }
 50 }
 51 int LCA(int x,int y)
 52 {
 53     while(top[x]!=top[y])
 54     {
 55         if(dep[top[x]]<dep[top[y]])
 56             swap(x,y); x=far[top[x]];
 57     }
 58     return dep[x]<dep[y]?x:y;
 59 }
 60 long long Dist(int x,int y)
 61 {
 62     int lca=LCA(x,y);
 63     return dis[x]+dis[y]-2*dis[lca];
 64 }
 65 void Mark(int nde,int fth)
 66 {
 67     sze[nde]=1,maxx[nde]=0;
 68     for(int i=p[nde];i;i=noww[i])
 69         if(goal[i]!=fth&&!vis[goal[i]])
 70         {
 71             Mark(goal[i],nde);
 72             sze[nde]+=sze[goal[i]];
 73             maxx[nde]=max(maxx[nde],sze[goal[i]]);
 74         }
 75     maxx[nde]=max(maxx[nde],sizz-sze[nde]);
 76     if(maxx[nde]<maxx[c]) c=nde;
 77 }
 78 void Create(int nde,int fth)
 79 {
 80     vis[nde]=true,fer[nde]=fth;
 81     for(int i=p[nde];i;i=noww[i])
 82         if(!vis[goal[i]])
 83         {
 84             sizz=sze[goal[i]],maxx[c=0]=sze[goal[i]];
 85             Mark(goal[i],0),Linka(nde,c,goal[i]),Create(c,nde);
 86         }
 87 }
 88 void Change(int nde,int tsk)
 89 {
 90     sum[nde]+=tsk; int mem=nde;
 91     while(fer[nde])
 92     {
 93         long long dist=Dist(fer[nde],mem)*tsk;
 94         dst[fer[nde]][0]+=dist,dst[nde][1]+=dist;
 95         sum[fer[nde]]+=tsk,nde=fer[nde]; 
 96     }
 97 }
 98 long long Getans(int nde)
 99 {
100     long long ret=dst[nde][0]; int mem=nde;
101     while(fer[nde])
102     {
103         long long dist=Dist(fer[nde],mem);
104         ret+=dst[fer[nde]][0]-dst[nde][1];
105         ret+=dist*(sum[fer[nde]]-sum[nde]);
106         nde=fer[nde];
107     }
108     return ret;
109 }
110 long long Query(int nde)
111 {
112     long long ret=Getans(nde);
113     for(int i=P[nde];i;i=Noww[i])
114         if(Getans(Val[i])<ret)
115             return Query(Goal[i]);
116     return ret;
117 }
118 int main()
119 {
120     scanf("%d%d",&n,&T);
121     for(int i=1;i<n;i++)
122         scanf("%d%d%d",&t1,&t2,&t3),Link(t1,t2,t3);
123     DFS(1,0,1),Gettop(1,1);
124     sizz=n,maxx[c=0]=n,Mark(1,0);
125     int mem=c; Create(c,0),c=mem;
126     while(T--)
127     {
128         scanf("%d%d",&t1,&t2);
129         Change(t1,t2),printf("%lld
",Query(c)); 
130     }
131     return 0;
132 }

View Code